适用场景：不断区间修改、区间询问。
假设我们要区间求和，\(tree\) 的含义：区间的和，其两个子节点为这个区间分为两半的和。
我们把一个数组 \(a\) 看作一颗树 \(tree\)，例：
1 1 2 3 3 3
对应的 \(tree\)（\(()\)里是编号，\([]\)里是对应的区间）：
(1)13[1,6]
/ \
(2)4[1,3] (3)9[4,6]
/ \ / \
(4)2[1,2] (5)2[3,3] (6)6[4,5] (7)3[6,6]
/ \ / \
(8)1[1,1] (9)1[2,2] (12)3[4,4] (13)3[5,5]
初始要先建树。
假如现在询问区间 \([3,5]\) 的和：
先到 \(1\) 号根节点：发现并没有全都不属于它，也没有都属于它，因此询问它的子节点 \(1 \times 2\) 和 \(1 \times 2 +1\) 寻找（\(2\) 和 \(3\)）
接下来到 \(2\) 号节点：发现并没有全都不属于它，也没有都属于它，因此询问它的子节点 \(2 \times 2\) 和 \(2 \times 2 +1\) 寻找（\(4\) 和 \(5\)）
接下来到 \(4\) 号节点：发现全都不属于它，直接跳过。
接下来到 \(5\) 号节点：发现都属于它，答案直接 \(+tree[5]\)（2）。
接下来到 \(3\) 号节点：发现并没有全都不属于它，也没有都属于它，因此询问它的子节点 \(3 \times 2\) 和 \(3 \times 2 +1\) 寻找（\(6\) 和 \(7\)）
接下来到 \(6\) 号节点：发现都属于它，答案直接 \(+tree[6]\)（6）。
接下来到 \(7\) 号节点：发现全都不属于它，直接跳过。
这样一来，最终的答案就是 \(tree[5]+tree[6]=2+6=8\)。
验证：\(2+3+3=8\)。
假如使 \([2,6]\) 的元素全部加 \(3\)。（未优化）
先到 \(1\) 号根节点：发现有部分属于它，因此 tree[1]+=(6-2+1)*3，由于要接着更新，因此继续更新它的子节点 \(1 \times 2\) 和 \(1 \times 2 +1\) 去更新（\(2\) 和 \(3\)）
接着到 \(2\) 号节点：发现有部分属于它，因此 tree[2]+=(3-2+1)*3，由于要接着更新，因此继续更新它的子节点 \(2 \times 2\) 和 \(2 \times 2 +1\) 去更新（\(4\) 和 \(5\)）
接着到 \(4\) 号节点：发现有部分属于它，因此 tree[4]+=(2-2+1)*3，由于要接着更新，因此继续更新它的子节点 \(4 \times 2\) 和 \(4 \times 2 +1\) 去更新（\(8\) 和 \(9\)）
接着到 \(8\) 号节点：发现没有部分属于它，因此退出。
接着到 \(9\) 号节点：发现有部分属于它，因此 tree[9]+=(2-2+1)*3，由于是叶子节点，退出。
接着到 \(5\) 号节点：发现有部分属于它，因此 tree[5]+=(3-3+1)*3，由于是叶子节点，退出。
接着到 \(3\) 号节点：发现有部分属于它，因此 tree[3]+=(6-4+1)*3，由于要接着更新，因此继续更新它的子节点 \(3 \times 2\) 和 \(3 \times 2 +1\) 去更新（\(6\) 和 \(7\)）
接着到 \(6\) 号节点：发现有部分属于它，因此 tree[6]+=(5-4+1)*3，由于要接着更新，因此继续更新它的子节点 \(6 \times 2\) 和 \(6 \times 2 +1\) 去更新（\(12\) 和 \(13\)）
接着到 \(12\) 号节点：发现有部分属于它，因此 tree[12]+=(4-4+1)*3，由于是叶子节点，退出。
接着到 \(13\) 号节点：发现有部分属于它，因此 tree[13]+=(5-5+1)*3，由于是叶子节点，退出。
接着到 \(7\) 号节点：发现有部分属于它，因此 tree[7]+=(6-6+1)*3，由于是叶子节点，退出。
最终：
(1)28[1,6]
/ \
(2)10[1,3] (3)18[4,6]
/ \ / \
(4)5[1,2] (5)5[3,3] (6)15[4,5] (7)6[6,6]
/ \ / \
(8)1[1,1] (9)4[2,2] (12)6[4,4] (13)6[5,5]
这样一来，时间复杂度达到 \(O(n \log n)\)，还不如直接枚举。
我们先看这一部分的代码：
#include<bits/stdc++.h>
using namespace std;
void pushup(int cur)
{
tree[cur]=tree[2*cur]+tree[2*cur+1];
return ;
}
void build(int cur,int lt,int rt) //建树
{
if(lt==rt)
{
tree[cur]=a[lt];
return ;
}
int mid=(lt+rt)>>1;
build(2*cur,lt,mid);
build(2*cur+1,mid+1,rt);
pushup(cur);
return ;
}
int query(int cur,int lt,int rt,int qx,int qy) //询问
{
if(rt<qx||qy<lt)
return 0;
if(qx<=lt&&rt<=qy)
return tree[cur];
int mid=(lt+rt)>>1;
return query(2*cur,lt,mid,qx,qy)+query(2*cur+1,mid+1,rt,qx,qy);
}
void update(int cur,int lt,int rt,int qx,int qy,int val) //修改
{
if(rt<qx||qy<lt)
return ;
if(lt==rt)
{
tree[cur]+=val;
return ;
}
int mid=(lt+rt)>>1;
update(2*cur,lt,mid,qx,qy,val);
update(2*cur+1,mid+1,rt,qx,qy,val);
pushup(cur);
return ;
}
线段树的优化：
我们发现修改的时候时间太长了，因此需要优化。
优化方法：打懒标记：
-
如果这个点一直在被更新而没有被询问，就会浪费很多的时间，因此打懒标记表示这里有 \(val\) 的值没有算。
-
标记下传：如果递归到这个点了，那么就要将这个点的懒标记打给他的子节点。
这样一来，询问的时间复杂度降到 \(O(\log n)\)。
接下来我们模拟一下：
假如使 \([2,6]\) 的元素全部加 \(3\)。（优化）
先到 \(1\) 号根节点：发现有部分属于它，接着更新它的子节点 \(1 \times 2\) 和 \(1 \times 2 +1\) 去更新（\(2\) 和 \(3\)），最终 tree[1]=tree[2]+tree[3]。
接着到 \(2\) 号节点：发现有部分属于它，接着更新它的子节点 \(2 \times 2\) 和 \(2 \times 2 +1\) 去更新（\(4\) 和 \(5\)），最终 tree[2]=tree[4]+tree[5]。
接着到 \(4\) 号节点：发现有部分属于它，接着更新它的子节点 \(4 \times 2\) 和 \(4 \times 2 +1\) 去更新（\(8\) 和 \(9\)），最终 tree[4]=tree[8]+tree[9]。
接着到 \(8\) 号节点：发现没有部分属于它，因此退出。
接着到 \(9\) 号节点：发现全属于它，因此 tree[9]+=(2-2+1)*3,tag[9]+=3，退出。
接着到 \(5\) 号节点：发现全属于它，因此 tree[5]+=(3-3+1)*3,tag[5]+=3，退出。
接着到 \(3\) 号节点：发现全属于它，因此 tree[3]+=(6-4+1)*3,tag[3]+=3，退出。
再询问区间 \([3,5]\) 的和：
先到 \(1\) 号根节点：发现并没有全都不属于它，也没有都属于它，因此询问它的子节点 \(1 \times 2\) 和 \(1 \times 2 +1\) 寻找（\(2\) 和 \(3\)）
接下来到 \(2\) 号节点：发现并没有全都不属于它，也没有都属于它，因此询问它的子节点 \(2 \times 2\) 和 \(2 \times 2 +1\) 寻找（\(4\) 和 \(5\)）
接下来到 \(4\) 号节点：发现全都不属于它，直接跳过。
接下来到 \(5\) 号节点：有标记，标记下传，（是叶子节点，相当于不传）发现都属于它，答案直接 \(+tree[5]\)。
接下来到 \(3\) 号节点：有标记，标记下传tree[2*3]+=(5-4+1)*3,tag[6]+=3;tree[2*3+1]+=(6-6+1),tag[7]+=3，发现并没有全都不属于它，也没有都属于它，因此询问它的子节点 \(3 \times 2\) 和 \(3 \times 2 +1\) 寻找（\(6\) 和 \(7\)）
接下来到 \(6\) 号节点：有标记，标记下传tree[2*6]+=(4-4+1)*3,tag[12]+=3;tree[2*6+1]+=(5-5+1),tag[13]+=3发现都属于它，答案直接 \(+tree[6]\)。
接下来到 \(7\) 号节点：有标记，标记下传，（是叶子节点，相当于不传）发现全都不属于它，直接跳过。
这样一来时间就快很多了。
代码：
#include<bits/stdc++.h>
using namespace std;
void pushup(int cur)
{
tree[cur]=tree[2*cur]+tree[2*cur+1];
return ;
}
void build(int cur,int lt,int rt) //建树
{
if(lt==rt)
{
tree[cur]=a[lt];
return ;
}
int mid=(lt+rt)>>1;
build(2*cur,lt,mid);
build(2*cur+1,mid+1,rt);
pushup(cur);
return ;
}
void addtag(int cur,int lt,int rt,int val) //打懒标记
{
tag[cur]+=val;
tree[cur]+=(rt-lt+1)*val;
return ;
}
void pushdown(int cur,int lt,int rt) //标记下传
{
int mid=(lt+rt)>>1;
addtag(2*cur,lt,mid,tag[cur]);
addtag(2*cur+1,mid+1,rt,tag[cur]);
tag[cur]=0;
return ;
}
int query(int cur,int lt,int rt,int qx,int qy) //询问
{
if(rt<qx||qy<lt)
return 0;
if(qx<=lt&&rt<=qy)
return tree[cur];
pushdown(cur,lt,rt);
int mid=(lt+rt)>>1;
return query(2*cur,lt,mid,qx,qy)+query(2*cur+1,mid+1,rt,qx,qy);
}
void update(int cur,int lt,int rt,int qx,int qy,int val) //修改
{
if(rt<qx||qy<lt)
return ;
if(qx<=lt&&rt<=qy)
{
addtag(cur,lt,rt,val);
return ;
}
pushdown(cur,lt,rt);
int mid=(lt+rt)>>1;
update(2*cur,lt,mid,qx,qy,val);
update(2*cur+1,mid+1,rt,qx,qy,val);
pushup(cur);
return ;
}