0.树状数组

常数极小，只能做前缀和，不过可以通过一些技巧让它做很多事情

比如，支持区间修改，区间查询： 

#include
      
       #include
       
        #include
        
         using namespace std;inline int rd(){  int ret=0,f=1;char c;  while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;  while(isdigit(c))ret=ret*10+c-'0',c=getchar();  return ret*f;}const int MAXN = 100005;typedef long long ll;int n,m;int t1[MAXN],t2[MAXN];int querys(int x){  int ret=0;  for(int i=x;i;i-=i&-i)ret+=(x+1)*t1[i]-t2[i];  return ret;}int query(int l,int r){  return querys(r)-querys(l-1);}void updates(int x,int w){  for(int i=x;i<=n;i+=i&-i)t1[i]+=w,t2[i]+=x*w;}void update(int l,int r,int w){  updates(l,w);updates(r+1,-w);}int main(){    n=rd();m=rd();    int q,x,y,z;    for(register int i=1;i<=n;i++)update(i,i,rd());    for(register int i=1;i<=m;i++){        q=rd();x=rd();y=rd();        if(q==1) z=rd(),update(x,y,z);        else cout<
         
          <
         
        
       
      

1.静态线段树

利用线段树是二叉树的性质，可以用二进制方便地找到左右儿子，缺点是本身值域不好扩充

2.动态线段树

类似平衡树，为用到的点开空间，数组大概开到O(nlogn)，非常好写

#include
      
       #include
       
        using namespace std;inline int rd(){  int ret=0,f=1;char c;  while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;  while(isdigit(c))ret=ret*10+c-'0',c=getchar();  return ret*f;}const int MAXN=5000005;const int MOD=1e9+7;typedef long long ll;ll val[MAXN],add[MAXN];int ch[MAXN][2],tot;inline int newnode(){
    return ++tot;}inline void pushup(int cur){val[cur]=val[ch[cur][0]]+val[ch[cur][1]];}inline void up(ll &x,ll y){(x+=y);x%=MOD;}inline void pushdown(int cur,int l,int r){  int mid=l+r>>1;  add[ch[cur][0]]+=add[cur];  add[ch[cur][1]]+=add[cur];  val[ch[cur][0]]+=add[cur]*(mid-l+1);  val[ch[cur][1]]+=add[cur]*(r-mid);  add[cur]=0;}void update(int L,int R,int &cur,int l,int r,ll w){  if(!cur)cur=newnode();  if(L<=l&&r<=R){val[cur]+=w*(r-l+1);add[cur]+=w;return;}  pushdown(cur,l,r);  int mid=l+r>>1;  if(L<=mid) update(L,R,ch[cur][0],l,mid,w);  if(mid< R) update(L,R,ch[cur][1],mid+1,r,w);  pushup(cur);}ll query(int L,int R,int cur,int l,int r){  if(!cur)cur=newnode();  if(L<=l&&r<=R)return val[cur];  pushdown(cur,l,r);  int mid=l+r>>1;ll ret=0;  if(L<=mid)ret+=query(L,R,ch[cur][0],l,mid);  if(mid 
       
      

3.线段树二分

类似平衡树找第k大，维护子树size信息

4.线段树合并

常用在权值线段树上（维护一个可重集合），有一个merge操作，实现nlogn合并两颗线段树

实际操作中，常是父节点合并子节点，可以不新建子节点，直接合并到父亲上，具体情况具体分析。

int merge(int u,int v){  if(!u)return v;  if(!v)return u;  int t=newnode();  val[t]=val[u]+val[v];  ch[t][0]=merge(ch[u][0],ch[v][0]);  ch[t][1]=merge(ch[u][1],ch[v][1]);}

5.线段树分治

谜