线段树--解决区间问题的数据结构，相比于树状数组，更具有普适性；
完全二叉树的性质：根节下标为1，，节点为 i 的节点，左子节点为2*i，右子节点为2*i+1；
代表nums中单个元素的节点tree[x]应当在树的最底层，即叶子节点；更大的区间从叶子节点开始向上构成；
代表区间【L，R】的节点 tree【i】，左子节点tree【2*i】表示区间【L，（L+R）/2】的区间和；右子节点tree【2*i+1】表示区间 【（L+R）/2 +1， R】的区间和；
初始化tree数组的大小 总是 令 其 为 4*n；类似于归并排序、快排的分治算法，将原问题不断的划分为左右子问题；
代码摘自：线段树从入门到急停 - 力扣（LeetCode）非常详细；
核心：一个就是注意单点修改时，递归结束条件的判断，是查询单点的话，就是 左右边界相等终止；查询区间和的话， 判断当前区间是否落在 所求范围内，是的话就加上这个区间；
另一个就是拓展：区间和数组可以替换为区间最值问题；求区间最大值、区间最小值等；
再一个就是区间修改问题，有两种，一种是增量式修改，因为注意到我们的区间和，若不关注每个具体的值，只是区间和的大小，我们无需每次都向下更新到叶子节点，否则会达到O(N)时间复杂度；因此 需要增加一个 数组，判断当前增量是否已经向下更新，我们称之为懒惰标记；； 第二种就是 覆盖式修改：将区间的值都修改为同一值，此时，我们不能依据增量式修改的方法，因为可能修改为0，而向下更新的标记 也是检查是否为0，从而 会产生冲突，所以另起一个数组，判断是否已经向下覆盖；；
代码实现：（此处将 两种修改方法写在一起了，建议分开写）
#include <bits/stdc++.h>
using namespace std;
class Segement_tree{
private:
vector<int>nums;
vector<int>tree;
vector<int>lazy;
vector<int>is_updated;
int n;
void pushUp(int i){
tree[i] = tree[2*i] + tree[2*i + 1];
}
void build(int left, int right, int i){
if(left == right){
tree[i] = nums[left];
}
int mid = (left + right) / 2;
build(left, mid, 2*i);
build(mid + 1, right, 2*i + 1);
pushUp(i);
}
/*单点修改*/
void add(int index, int x, int left, int right, int i){
if(left == right){
tree[i] += x;
return;
}
int mid = (left + right)/2;
if(index <= mid){
add(index,x,left,mid,2*i);
}else{
add(index,x,mid+1,right,2*i+1);
}
pushUp(i);
}
void update(int index,int x,int left, int right,int i){
if(left == right){
tree[i] = x;
return;
}
int mid = (left + right) /2;
if(index <= mid){
update(index,x,left,mid,2*i);
}else{
update(index,x,mid+1,right,2*i+1);
}
pushUp(i);
}
int query(int index,int left,int right, int i){
if(left == right) return tree[i];
int mid = (left + right) /2;
if(index <= mid){
return query(index,left,mid,2*i);
}else{
return query(index,mid+1,right,2*i+1);
}
}
/*区间求和*/
int sum(int left, int right, int s, int t, int i){
if(left <= s && t <= right) return tree[i];
int mid = (s + t) /2;
int res = 0;
if(left <= mid){
res += sum(left,right, s, mid, 2*i);
}
if(right > mid){
res += sum(left,right, mid+1, t, 2*i+1);
}
return res;
}
/*区间修改： 增量式 */
void add(int left, int right, int x,int s, int t, int i){
if(left <= s && t <= right){
tree[i] += (t-s+1)*x;
if(s != t) lazy[i] += x;
return;
}
int mid = (s + t)/2;
if(lazy[i] != 0) pushDown(s,mid,t,i);
if(left <= mid) add(left,right,x,s,mid,2*i);
if(right > mid) add(left,right,x,mid+1,t,2*i+1);
pushUp(i);
}
void pushDown(int s,int mid, int t,int i){
tree[2*i] += (mid-s+1)*lazy[i];
lazy[2*i] += lazy[i];
tree[2*i+1] += (t-mid)*lazy[i];
lazy[2*i+1] += lazy[i];
lazy[i] = 0;
}
/*区间修改： 覆盖式 */
void update(int left, int right,int x,int s,int t,int i){
if(left <= s && t <= right){
tree[i] = (t-s+1)*x;
if(s != t){
lazy[i] = x;
is_updated[i] = true;//未推送
}
return;
}
int mid = (s+t)/2;
if(is_updated[i]) pushDown1(s,mid,t,i);
if(left <= mid) update(left,right,x,s,mid,2*i);
if(right > mid) update(left,right,x,mid+1,t,2*i+1);
pushUp(i);
}
void pushDown1(int s,int mid,int t,int i){
tree[2*i] = (mid - s + 1)* lazy[i];
lazy[2*i] = lazy[i];
is_updated[2*i] = true;
tree[2*i+1] = (t - mid) * lazy[i];
lazy[2*i+1] = lazy[i];
is_updated[2*i+1] = true;
is_updated[i] = false;
lazy[i] = 0;
}
public:
Segement_tree(vector<int>& nums){
this->n = nums.size();
this->nums = nums;
this->tree.resize(4*n, 0);
this->lazy.resize(4*n, 0);
this->is_updated.resize(4*n, 0);
build(0, n-1, 1);
}
/*单点修改*/
void add(int index, int x){
add(index,x,0,n-1,1);
}
void update(int index,int x){
update(index,x,0,n-1,1);
}
int query(int index){
return query(index, 0, n-1,1);
}
/*区间求和*/
int sum(int left,int right){
return sum(left,right,0, n-1,1);
}
/*区间修改 ： 增量式*/
void add(int left,int right,int x){
add(left,right,x,0,n-1,1);
}
/*区间修改： 覆盖式 */
void update(int left,int right, int x){
update(left,right,x,0,n-1,1);
}
};
int main(){
system("pause");
return 0;
}
标签：lazy,right,int,线段,tree,mid,left From： https://www.cnblogs.com/xuan01/p/17397312.html