线段树是一类处理区间问题的优秀算法，通过用空间换时间来得到相对平均的复杂度。
同时，也是一个 OIer 从萌新到提高的重要过渡。
1.线段树的基本概念
不难看出线段树是一棵完全二叉树，故我们可以用一维数组存整棵树。
显然，根节点的值等于左右两个节点之和，即
\(tree[i].sum = tree[i * 2].sum + tree[i * 2 + 1].sum\)
建树方法：递归建树。
inline void build(int i, int l, int r){
tree[i].l = l, tree[i].r = r;
if(l == r){
tree[i].sum = input[l];
return ;
}
int mid = (l + r) >> 1;
build(i * 2, l, mid), build(i * 2 + 1, mid + 1, r);
tree[i].sum = tree[i*2].sum + tree[i*2+1].sum;
}
2.线段树基本操作
（1）区间查询
分三种情况：
1.查询区间在同一个节点，直接返回。
2.查询区间与这个节点有交集，取 mid ，r 小于递归左边，l 大于递归右 边，否则两边都要递归。
3.查询区间与这个节点交集为空，不存在，跳过。
inline int query(int i, int l, int r){
if(tree[i].l >= l && tree[i].r <= r) return tree[i].sum;
if(tree[i].r < l || tree[i].l > r) return 0;
int s = 0;
if(tree[i*2].r >= l) s += query(i * 2, l, r);
if(tree[i*2+1].l <= r) s += query(i * 2 + 1, l, r);
return s;
}
（2）单点修改
修改这个区间的单点，相对简单很多，把区间的第 dis 位加上 k 。从根节点开始，看这个 dis 是在左儿子还是在右儿子，在哪往哪跑，返回的时候还是按照 tree[i].sum=tree[i2].sum+tree[i2+1].sum 更新所有路过点。
inline void add(int i, int dis, int k){
if(tree[i].l == tree[i].r){//如果是叶子节点，那么说明找到了
tree[i].sum += k;
return ;
}
if(dis <= tree[i * 2].r) add(i * 2, dis, k);//在哪往哪跑
else add(i * 2 + 1, dis, k);
tree[i].sum = tree[i * 2].sum + tree[i * 2 + 1].sum;//返回更新
return ;
}
（3）区间修改
区间修改和单点查询，我们的思路就变为：如果把这个区间加上 k ，相当于把这个区间涂上一个 k 的标记，然后单点查询的时候，就从上跑道下，把沿路的标记加起来就好。这里面给区间贴标记的方式与上面的区间查找类似，原则还是那三条，只不过第一条：如果这个区间被完全包括在目标区间里面，直接返回这个区间的值变为了如果这个区间如果这个区间被完全包括在目标区间里面，讲这个区间标记 k
```cpp
void modify(int p, int l, int r, int k) {
if(tr[p].l >= l && tr[p].r <= r) {
tr[p].num += k;
return ;
}
int mid = tr[p].l + tr[p].r >> 1;
if(l <= mid) modify(p << 1, l, r, k);
if(r > mid) modify(p << 1 | 1, l, r, k);
}
（4）单点查询
void query(int p, int x) {
ans += tr[p].num;
if(tr[p].l == tr[p].r) return;
int mid = tr[p].l + tr[p].r >> 1;
if(x <= mid) query(p << 1, x);
else query(p << 1 | 1, x);
}
3.线段树进阶操作
“懒标记” lazytag ，来记录这个区间，修改的时候，按照如下原则：
1、如果当前区间被完全覆盖在目标区间里，讲这个区间的 sum+k(tree[i].r-tree[i].l+1)
2、如果没有完全覆盖，则先下传懒标记
3、如果这个区间的左儿子和目标区间有交集，那么左儿子，如果右儿子和目标区间有交集，那么搜索右儿子
注意处理完这些以后，还是要按照
tree[i].sum=tree[i2].sum+tree[i*2+1].sum的原则返回。
void push_down(int i) {
if(tree[i].lz != 0){
tree[i*2].lz += tree[i].lz;
tree[i*2+1].lz += tree[i].lz;
int mid = (tree[i].l + tree[i].r) / 2;
tree[i*2].sum += tree[i].lz * (mid - tree[i * 2].l + 1);
tree[i * 2 + 1].sum += tree[i].lz * (tree[i * 2 + 1].r - mid);
tree[i].lz = 0;
}
return ;
}
void add(int i, int l, int r, int k) {
if(tree[i].r <= r && tree[i].l >= l){
tree[i].sum += k * (tree[i].r - tree[i].l + 1);
tree[i].lz += k;//记录lazytag
return ;
}
push_down(i);//向下传递
if(tree[i * 2].r >= l) add(i * 2, l, r, k);
if(tree[i * 2 + 1].l <= r) add(i * 2 + 1, l, r, k);
tree[i].sum = tree[i * 2].sum + tree[i * 2 + 1].sum;
return ;
}
inline int search(int i, int l, int r){
if(tree[i].l >= l && tree[i].r <= r) return tree[i].sum;
if(tree[i].r < l || tree[i].l > r) return 0;
push_down(i);
int s = 0;
if(tree[i * 2].r >= l) s += search(i * 2, l, r);
if(tree[i * 2 + 1].l <= r) s += search(i * 2 + 1, l, r);
return s;
}