本来想练练线段树的，没想到有许多细节忘了，加上今天的金工实习坐牢坐穿了，于是再复习一下吧。

首先介绍一下树状数组（貌似第一篇就讲了，不过那个东西真是一坨Shit,当时还没有怎么理解就写了）

首先它的复杂度为logn，主要功能是动态的给某个位置加上一个数以及求某一个前缀和。

我们发现它包含于线段树，不过他的常数小并且实现简单。

我们先不讲原理，下面直接看它的实现方式（注意：下标从1开始）：

其中第0层即它没有2的因子（奇数）。

第二层即有2^1，但没有2^2的数，依次类推。。。。。

我们假设x二进制最后有k个0，那么它表示从x-2^k---x的区间和。

即c[x]=(x-lowbit(x),x]（c[x]表示其代表的值）。

这样子，我们如何求某一个前缀和：c[x]+c[x-lowbit[x]]+.....即可。

那么怎么更新？假如更新7，那么8，16的值也需要更新。可得我们从它开始依次加lowbit即可（证明省略）

来个模板题：

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m,a[N],tr[N];
int lowbit(int x){return x&(-x);
}
void add(int x,int v){for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=v;
}
int query(int x){int res=0;for(int i=x;i>0;i-=lowbit(i)){res+=tr[i];}return res;
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) add(i,a[i]);while(m--){int k,x,y;scanf("%d%d%d",&k,&x,&y);if(k==0) printf("%d\n",query(y)-query(x-1));else add(x,y);}
}

来个简单的应用（二维降一维）：

其实我们发现，在时间的顺序下问题就是求1---xi的前缀和（没有给t的话就先排一下序，这样子就十分巧妙地转化成了一维，这样就转化成了刚才的模板题。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=32010;
int n,x,y,tr[N],level[N];
int lowbit(int x){return x&(-x);
}
int add(int x){for(int i=x;i<=N;i+=lowbit(i)) tr[i]++;
}
int sum(int x){int res=0;for(int i=x;i;i-=lowbit(i)) res+=tr[i];return res;
}
int main(){cin>>n;for(int i=0;i<n;i++){scanf("%d%d",&x,&y);x++;level[sum(x)]++;add(x);}for(int i=0;i<n;i++) printf("%d\n",level[i]);
}

接下来个线段树的一个模板题练练手：

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m,w[N];
struct node{int l,r;int maxv;
}tr[N*4];
void build(int u,int l,int r){if(l==r) tr[u]={l,r,w[l]};else{tr[u]={l,r};int mid=(l+r)/2;build(u<<1,l,mid);build(u<<1|1,mid+1,r);tr[u].maxv=max(tr[u<<1].maxv,tr[u<<1|1].maxv);}
}
int query(int u,int l,int r){if(tr[u].l>=l&&tr[u].r<=r) return tr[u].maxv;int mid=tr[u].l+tr[u].r>>1;int maxv=INT_MIN;if(l<=mid) maxv=query(u<<1,l,r);if(r>mid) maxv=max(maxv,query(u<<1|1,l,r));return maxv;
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++) scanf("%d",&w[i]);build(1,1,n);int l,r;while(m--){scanf("%d%d",&l,&r);printf("%d\n",query(1,l,r));}
}

（这个静态的题用线段树纯属没事找事）