线段树与树状数组都是十分经典的数据结构，其实能用树状数组解决的问题也都能用线段树解决，但线段树相比于树状数组常数较大。
单点修改区间查询
线段树做法，树状数组做法，其实单纯实现这个还是用树状数组较好（毕竟常数小还好写）
区间修改区间查询
权值线段树/树状数组
其实就是正常线段树/树状数组维护的定义域下标为正常下标，现在为权值。
线段树专讲
线段树其实就是通过几个小区间的信息，合并出一个大区间的信息，所以线段树的运算要满足结合律。对不同题目，我们要考虑记录不同的信息，要合并它们。
- 动态开点线段树
就是定义域下标范围太大，不能把整棵树开满，那就用一个点，看一个点
code：
点击查看代码
struct Segment_Tree {
int ncnt=0;
struct Node { int son[2];} f[10000010];
int newnode_() { return ncnt++;}
int modify_(int x,int l,int r,int pos,int md) {
if (!x) x=newnode_();
if (l==r) { return 0;}
int mid=(l+r)>>1;
if (pos<=mid) f[x].son[0]=modify_(f[x].son[0],l,mid,pos,md);
else f[x].son[1]=modify_(f[x].son[1],mid+1,r,pos,md);
pushup_(x);
return x;
}
} st;
- 线段树二分，线段树上二分，听起来挺高深，其实就是像二分一样每次判断查询区间往右挪还是往左挪，然后想应该去的方向递归。
- 线段树维护区间最大子段和
线段树每个点维护四个信息，区间最大子段和，最大前缀，最大后缀，区间和。用这几个条件合并（例） - 结合树
对一棵子树修改/查询，由于字数内dfs序是连续的，用线段树维护。（例） - 区间修时取模操作
由于每次取模至少减半，所以一个数最多被修改\(log\)次，区间修时可以递到每个l==r更改，复杂度\(log^{2}\)(例） - 当我们每次对区间增加一个等差数列，求单点，可以线段树维护差分数组。（例）