网站开发一般有几个服务器,响应式网站设计与实现论文,功能型网页设计,淄博团购网站建设前段时间写过一篇关于树状数组的博客树状数组#xff0c;今天我们要介绍的是线段树#xff0c;线段树比树状数组中的应用场景更加的广泛。这些问题也是在leetcode 11月的每日一题频繁遇到的问题#xff0c;实际上线段树就和红黑树 、堆一样是一类模板#xff0c;但是标准库… 前段时间写过一篇关于树状数组的博客树状数组今天我们要介绍的是线段树线段树比树状数组中的应用场景更加的广泛。这些问题也是在leetcode 11月的每日一题频繁遇到的问题实际上线段树就和红黑树 、堆一样是一类模板但是标准库里面并没有所以题目的代码量会比较大。如果我们深刻了解了其中的原理刷到的时候默写出来问题也不是很大。 文章目录 问题引入线段树的引入树节点数据结构建立一个线段树线段树的查询线段树的区间修改小结Lazy标记区间修改向下传递 代码 动态开点完整模板总结例题 如果没有看过线段树博客的先去看那个再来看这个问题
问题引入
在树状数组中我们的问题是 给你一个数组 nums 请你完成两类查询。 其中一类查询要求 更新 数组 nums 下标对应的值 另一类查询要求返回数组 nums 中索引 left 和索引 right 之间 包含 的nums元素的 和 其中 left right 实现 NumArray 类 NumArray(int[] nums) 用整数数组 nums 初始化对象void update(int index, int val) 将 nums[index] 的值 更新 为 valint sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间 包含 的nums元素的 和 即nums[left] nums[left 1], …, nums[right] 在这个问题中我们对区间的修改始终是单点修改如果我们想修改一个区间的值指给这个区间的所有值都加、减一个数这时候树状数组只能遍历这个区间然后对区间每一个数做单点修改这样修改的时间复杂度就是M*logNM为区间长度N为整个区间的大小。
但是如果用线段树来解决每次区间修改的时间复杂度可以降到logN
线段树的引入
线段树不像前面介绍的树状数组一样树状数组逻辑结构是树但是物理结构是一个数组。而线段树是一个真正的树型结构。 假设我们有一个长度为10 的数组。如果我们要构建一个线段树一定是下面这个结构 我们观察可以发现
每个节点都是维护的一个区间的统计值可以是区间和 区间的最大值 、最小值所有的叶子节点的区间长度均为1也就是数组的一个单点元素的值如果一个节点有子节点且区间为[left,right] ,那么子节点的区间分别为[left,mid]、[mid1,right] 其中mid(leftright)/2
树节点数据结构
根据上图我们很轻松的就可以定义出树节点的数据结构。
struct STNode {STNode* left; // 左节点STNode* right; // 右节点int val; // 维护的区间的值可能是区间和、区间的最值int add; //这个是lazy标记我们后面会介绍这里我们可以先忽略
};建立一个线段树
实际上这个建立树的过程后面会讲到线段树的动态开点否则leetcode的内存会爆掉。 假设我们给定一个数组要求你根据这个数组构建一个线段树这个线段树的每一个区间维护的都是这个区间的区间和。 class SegmentTree {
public:void PushUp(STNode *cur) {cur-val cur-left-val cur-right-val;}void BuildTree(const vectorint v) {N v.size(); // 用于记录线段树查询区间的大小functionvoid(int,int,STNode*) dfs [](int l,int r,STNode* cur) {if (l r) {curnew STNode{ nullptr,nullptr,v[l],0};return;}int mid (r - l) / 2 l;curnew STNode{ nullptr,nullptr,0,0 };dfs(l, mid, cur-left);dfs(mid 1, r, cur-right);PushUp(cur);};dfs(0, v.size() - 1, root);}
private:STNode* root nullptr; // 根节点int N; // 用于记录线段树查询区间的大小
};注意这个递归建立线段树一定要选对遍历的方式——后续遍历因为只要一个节点有子节点那么他的值一定是在两个子节点已经遍历完了之后才能确定这符合后续遍历的定义先遍历完左子树和右子树最后两个子树的信息汇总到根节点。 这样一颗完整的线段树便可以确定。注意这里的PushUp函数就是遍历完左右子树后的更新根节点由于后面的查询和区间修改都需要这个操作所以这里需要重点理解一下
线段树的查询
线段树查询的思路是 假设被查询的区间是[left,right] ,当前节点的区间为 [start , end] 如果查询的区间正好包括了节点所代表的区间即left start rightend 则返回区间的值如果查询的区间不包含节点的区间那么我们可以通过 mid (start end)/2 求出其两个子节点的区间然后将判断查询区间和哪个子节点相交继续向子节点向下递归,直到找到第一种情况为止
对于区间查询比方说我们需要查询[2,6]这个区间的区间和红色的是查询的路径蓝色是最终组成这个[2,6]区间的节点也是查询的结束的地方。
很简单我们顺着上面的逻辑很快就能写出查询某个区间的代码这里就不做过多的解释了
class SegmentTree {
public:void PushUp(STNode *cur) {cur-val cur-left-val cur-right-val;}// 区间查询int Query(int left,int right) {// left right 为要查询的区间 start end 为当前节点所维护的区间functionint(int, int, int, int, STNode*) dfs [](int left, int right,int start ,int end, STNode* cur) {if (left start right end) {return cur-val;}int mid (end - start) / 2 start;int ansl 0, ansr 0;if (left mid) {ansl dfs(left, right, mid 1, end, cur-right);}else if (right mid) {ansr dfs(left, right, start, mid, cur-left);}else {ansl dfs(left, right, mid 1, end, cur-right);ansr dfs(left, right, start, mid, cur-left);}//PushUp(cur); // 向上更新return ansl ansr;};return dfs(left, right, 0, N, root);}
private:STNode* root nullptr; // 根节点int N; // 用于记录线段树查询区间的大小
};线段树的区间修改
这里我们讨论的区间修改只的是让区间[left,right] 都加上或减去一个val 到这里我们来分析一下如何进行区间修改这里我们和区间查询的思路一致 假设被查询的区间是[left,right] ,当前节点的区间为 [start , end] 如果查询的区间正好包括了节点所代表的区间即left start rightend 则更新区间的值但是这里注意我们更新了大区间的值下面他的所有小区间都需要更新 下面的代码PushDown函数就是处理这个问题的。如果查询的区间不包含节点的区间那么我们可以通过 mid (start end)/2 求出其两个子节点的区间然后将判断查询区间和哪个子节点相交继续向子节点向下递归直到找到第一种情况为止
class SegmentTree {
public:void PushUp(STNode *cur) {cur-val cur-left-val cur-right-val;}void PushDown(int l,int r,STNode* cur,int val) {if (cur nullptr) {return;}cur-val (r - l1) * val;int mid (r - l) / 2 l;PushDown(l, mid, cur-left, val);PushDown(mid 1, r, cur-right, val);}void Update(int left, int right,int val) {// left right 为要查询的区间 start end 为当前节点所维护的区间 val为区间修改的值functionvoid(int, int, int, int, int, STNode*) dfs [](int left, int right, int start, int end, int val, STNode* cur) {if (left start right end) {PushDown(start, end, cur, val); // 将cur区间所有子节点全部更新了return;}int mid (end - start) / 2 start;int ansl 0, ansr 0;if (left mid) {dfs(left, right, mid 1, end, val, cur-right);}else if (right mid) {dfs(left, right, start, mid, val, cur-left);}else {dfs(left, right, mid 1, val, end, cur-right);dfs(left, right, start, mid, val, cur-left);}PushUp(cur); // 向上更新 值因为修改了子区间 其所有父区间都会被修改};dfs(left, right, 0, N,val, root);}
private:STNode* root nullptr; // 根节点int N; // 用于记录线段树查询区间的大小
};小结
代码写到这里线段树的功能已经被我们全部实现了但是我们回国头来看一下线段树的实现思路看看是否还有优化的地方。 我们主要把目光放在 线段树的修改上面我们上面线段树的修改的思路实际上和树状数组的遍历区间的单点修改是没有什么区别的并没有什么优势时间复杂度都是时间复杂度就是M*logNM为区间长度N为整个区间的大小。 所以我们接下来要介绍一下优化方案——Lazy标记
Lazy标记
区间修改
我们的区间修改 的优化方案 主要集中在PushDown这个函数上我们当前的区间修改对于节点的区间被查询区间包含的情况是修改当前节点并将修改传递给当前节点的每一个子节点。而我们的Lazy标记实际上就是优化这一步。
实际上我们发现我们修改完当前的节点时候对于节点的区间被查询区间包含的情况实际上并不需要将子节点修改或者换一种说法不需要立刻修改所有的子节点我们可以设置一个Lazy标记。 这个Lazy标记的定义是 记录所有子节点的区间应当被修改但是未被修改的值。这些值先由父节点记录等到后面如果要访问到下面的节点的时候顺路把标记带下去 这些懒标记我们可以在后面查询的时候比方说访问到懒标记所在节点的子节点的时候在去把Lazy标记下放也就是把Lazy标记传递到子节点。
假设我有一个全0的长度位10 的数组需要更新区间[0,6]
这时候按照 Lazy标记的 定义我们遍历到区间包含节点区间的时候就不必向下更新了而是直接修改节点的Lazy标记 这样 我们回过头来看树节点的设计中我们一直都留着一个add这个就是每个树节点的Lazy标记
struct STNode {STNode* left;STNode* right;int val;int add; // Lazy标记
};我们更新[0,6]这个区间递归结束的节点始终满足节点区间被查询区间所包含注意更新的值为区间长度*val
但是别忘了最后的回溯更新所以这次区间更新的最终结果是黄色的线代表回溯更新的路线 向下传递
假设我们这时候需要查询或者更新[0,2] 我们这里以更新区间[0,2]让区间里面的每一个元素加1为例
当我们遍历到区间[0,2]的时候这时候就需要下放Lazy标记到他的子节点注意这里下放的Lazy标记代表节点区间[0,2]和节点区间[3,5]理论上应该区间每一个元素1所以每个节点的val需要3然后两个子节点lazy标记需要加上父节点的Lazy标记注意不是直接赋值因为这两个子节点的子节点并没有更新Lazy标记。最后记得把父节点区间[0,5]的lazy标记置0
然后由于我们还需要更新[0,2]节点的值所以我们直接更新节点区间[0,2]lazy标记让Lazy标记1因为要更新区间[0,2]让区间每一个元素加1
最后别忘了回溯的时候更新父节点的val
代码
从上面的流程我们可以看出Lazy标记实际上是一种向下传递所以我们只需要修改PushDown函数的逻辑既可那我们就要思考一个问题何时需要向下传递 答案很简单当查询区间不包含当前节点区间的时候这时候查询的区间一定在当前区间的子节点中所以需要向下递归所以在向下递归之前我们需要下传Lazy标记 这句话需要好好理解一下。 void PushDown(int l, int r, STNode* cur) {if (cur-add 0) // 如果当前节点没有Lazy标记则不需要下传直接返回return;int mid (r - l) / 2 l;// 将父节点的 Lazy 标记下传到cur-left-add cur-add;cur-right-add cur-add;cur-left-val (mid - l 1) * cur-add;cur-right-val (r - mid) * cur-add;cur-add 0;}然后相应的Query和Update函数都要做出相应的修改 void Update(int left, int right, int val) {// left right 为要查询的区间 start end 为当前节点所维护的区间 val为区间修改的值functionvoid(int, int, int, int, int, STNode*) dfs [](int left, int right, int start, int end, int val, STNode* cur) {if (left start right end) {cur-val (end - start 1) * val;cur-add val;return;}// 走到这里代表要查询的区间[left,right]一定在cur节点的子节点中 一定要理解PushDown(start, end, cur);int mid (end - start) / 2 start;int ansl 0, ansr 0;if (left mid) {dfs(left, right, mid 1, end, val, cur-right);}else if (right mid) {dfs(left, right, start, mid, val, cur-left);}else {dfs(left, right, mid 1, end, val, cur-right);dfs(left, right, start, mid, val, cur-left);}PushUp(cur); // 向上更新父节点};dfs(left, right, 0, N, val, root);}int Query(int left, int right) {// left right 为要查询的区间 start end 为当前节点所维护的区间functionint(int, int, int, int, STNode*) dfs [](int left, int right, int start, int end, STNode* cur) {if (left start right end) {return cur-val;}// 走到这里代表要查询的区间[left,right]一定在cur节点的子节点中 一定要理解PushDown(start, end, cur);int mid (end - start) / 2 start;int ansl 0, ansr 0;if (left mid) {ansl dfs(left, right, mid 1, end, cur-right);}else if (right mid) {ansr dfs(left, right, start, mid, cur-left);}else {ansl dfs(left, right, mid 1, end, cur-right);ansr dfs(left, right, start, mid, cur-left);}PushUp(cur);return ansl ansr;};return dfs(left, right, 0, N, root);}动态开点
到这里实际上线段树就已经结束了但是做题的时候如果这样搞理论上应该是无法通过的因为题目的区间都是很大的一般题目给的区间都是[1,1000000000]如果我们按照上面的构建线段树的方法内存应该无法通过。与是这里我们又有了一种新的方法——动态开点
我们设想如果我们要查询的区间落在[1,1000000000]上如果我们上来就开辟1000000000个节点构成线段树设想下面这种情况我们的区间查询和更新都集中在[0,5000000000] 上而区间[500000001,1000000000]只被查询过一次那么区间[500000001,1000000000]下面500000000个节点实际上是不用开辟的
空间上是极大的浪费我们这里的处理的方法和Lazy标记一样就是当我们用到该节点的时候我们再去创建该节点。 而我们何时知道需要访问到子节点 也就是查询区间不包含当前节点区间的时候意味着目标节点肯定在子节点中这时候我们再去开辟子节点 我们把这部分逻辑放在PushDown函数里面去实现。
void PushDown(int l, int r, STNode* cur) {// 创建子节点 如果没有的话if (cur-left nullptr) cur-left new STNode{ nullptr,nullptr,0,0 };if (cur-right nullptr) cur-right new STNode{ nullptr,nullptr,0,0 };if (cur-add 0)return;int mid (r - l) / 2 l;cur-left-add cur-add;cur-right-add cur-add;cur-left-val (mid - l 1) * cur-add;cur-right-val (r - mid) * cur-add;cur-add 0;}完整模板
到这里线段树的模板就已经写完了
struct STNode {STNode* left;STNode* right;int val 0;int add;
};class SegmentTree {
public:void PushUp(STNode* cur) {cur-val cur-left-val cur-right-val;}SegmentTree() {N 1000000000;root new STNode{ nullptr,nullptr,0,0 };}void PushDown(int l, int r, STNode* cur) {if (cur-left nullptr) cur-left new STNode{ nullptr,nullptr,0,0 };if (cur-right nullptr) cur-right new STNode{ nullptr,nullptr,0,0 };if (cur-add 0)return;int mid (r - l) / 2 l;cur-left-add cur-add;cur-right-add cur-add;cur-left-val (mid - l 1) * cur-add;cur-right-val (r - mid) * cur-add;cur-add 0;}void Update(int left, int right, int val) {// left right 为要查询的区间 start end 为当前节点所维护的区间 val为区间修改的值functionvoid(int, int, int, int, int, STNode*) dfs [](int left, int right, int start, int end, int val, STNode* cur) {if (left start right end) {cur-val (end - start 1) * val;cur-add val;return;}PushDown(start, end, cur);int mid (end - start) / 2 start;int ansl 0, ansr 0;if (left mid) {dfs(left, right, mid 1, end, val, cur-right);}else if (right mid) {dfs(left, right, start, mid, val, cur-left);}else {dfs(left, right, mid 1, end, val, cur-right);dfs(left, right, start, mid, val, cur-left);}PushUp(cur);};dfs(left, right, 0, N, val, root);}int Query(int left, int right) {// left right 为要查询的区间 start end 为当前节点所维护的区间functionint(int, int, int, int, STNode*) dfs [](int left, int right, int start, int end, STNode* cur) {if (left start right end) {return cur-val;}PushDown(start, end, cur);int mid (end - start) / 2 start;int ansl 0, ansr 0;if (left mid) {ansl dfs(left, right, mid 1, end, cur-right);}else if (right mid) {ansr dfs(left, right, start, mid, cur-left);}else {ansl dfs(left, right, mid 1, end, cur-right);ansr dfs(left, right, start, mid, cur-left);}PushUp(cur);return ansl ansr;};return dfs(left, right, 0, N, root);}private:STNode* root nullptr; // 根节点int N; // 用于记录线段树查询区间的大小
};总结
但是在做题的时候还是会对模板进行修改修改的点主要在区间val的意义上我们这里模板里面val代表的是区间和但后面题目里面可能是 区间最大值 、区间最小值…但是万变不离其宗线段树的结构是不会变的。
例题
我的日程安排表 1 我的日程安排表 II 我的日程安排表 III 715. Range 模块
