ST表
st表可以解决区间最值的问题。可以做到O(nlogn)预处理 ，O（1）查询，但是不支持修改。
st表的大概思路就是用st[i][j]来表示从i开始的2的j次方个树中的最值，查询时就从左端点开始，找到区间长度是2的多少次方，然后进行查询。然而，很明显，我们要查询的区间长度不一定是2的多少次幂。那怎么做到O(1)查询呢，这就要用到最值的特性。
如图，假如我们要查询2到7之间的最大值，但是7-2+1在22与23之间，我们选择22，也就是st[2][2],那剩下的6,7怎么办，我们考虑倒着从7往回算，也就是在st[7-22][2]与st[2][2]取max作为从2到7的最大值。
首先，进行预处理，st[i][j]表示从i开始的2的j次方，那么st[i][j]就应该是从i开始2的j-1次方与从i+2j-1开始的2的j-1次方中的最大值，那么进行递推就好了。
代码：
#include<cstdio>
#include<iostream>
using namespace std;
const int N=;
int n,m,a[N],st[N][],log[N],cf[];
void pre()
{
log[]=;
log[]=;
for(int i=;i<=n;++i)
{
log[i]=log[i/]+;
}
cf[]=;
cf[]=;
for(int i=;i<=log[n]+;++i)
{
cf[i]=cf[i-]*;
}
}
int read()
{
int x=,f=;char c=getchar();
while(c<''||c>'')
{
if(c=='-') f=-;
c=getchar();
}
while(c>=''&&c<='')
{
x=x*+c-'';
c=getchar();
}
return x;
}
int ff(int x,int y)
{
int l=y-x+,k=log[l];
int f=max(st[x][k],st[y-cf[k]+][k]);
return f;
}
int main()
{
n=read(),m=read();
pre();
for(int i=;i<=n;++i)
{
st[i][]=a[i]=read(); } for(int j=;j<=log[n];++j)
{
for(int i=;i+cf[j]-<=n;++i)
{
st[i][j]=max(st[i][j-],st[i+cf[j-]][j-]);
}
}
for(int i=,x,y;i<=m;++i)
{
x=read(),y=read();
cout<<ff(x,y)<<"\n";
}
return ;
}
树状数组
其实，树状数组的原理我并不是很懂，但是因为其短小精炼的代码，令我非常喜欢。。。。
树状数组不需要预处理，只有修改与查询两种操作。修改可以是加或减一个值，查询的是一个区间和。
首先我们需要一个数组tree。
然后就是修改，只需写一个几行的子函数，然后将修改元素的下标和要加的元素传入函数，然后奇迹就发生了。
查询传入要查询的下标就可以查询从1到改元素之间的区间和，如果查询从l到r，只需分别求出其从以到他们的区间和，然后相减即可，类似于前缀和。具体的都在代码里了。
#include<cstdio>
#include<iostream>
using namespace std;
const int N=;
int tree[N],n,m;
void add(int a,int pos)
{
while(pos<=n){
tree[pos]+=a;
pos+=pos&-pos;
}
}
int cc(int pos)
{
int ans=;
while(pos>=){
ans+=tree[pos];
pos-=pos&-pos;
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=,x;i<=n;++i)
{
scanf("%d",&x);
add(x,i);
}
for(int i=,bz,x,y;i<=m;++i){
scanf("%d%d%d",&bz,&x,&y);
if(bz==)
add(y,x);
else{
int kk=cc(y),zz=cc(x-);
printf("%d\n",kk-zz);
}
}
return ;
}
上面讲的是树状数组的单点修改和区间查询，下面写一下，树状数组的区间修改单点查询。
首先介绍一下差分数组和前缀和。
前缀和就是记录前几个数的和，差分数组呢就是记录当前位置减去前一个位置的数的差。
然后要用到一个前缀和与差分数组的性质：前缀和数组的差分数组是原数组，差分数组的前缀和是原数组。
证明很显然，动手一推就知道了。
那么这与树状数组有什么关系呢，通过上面那个树状数组，我们知道，树状数组可以记录前几个数的和，现在我们要做的是区间修改和单点查询。
这时又要用到一个差分数组的一个性质。
差分数组进行区间加减时比较方便，比如如果将从i到j之间的数加k，那么只需将他们的差分数组i位置+k，并且将j+1位置的数-k即可。
证明同样很显然，动手推。
那么这就有联系了，我们树状数组维护的相当于是前缀和，然后我们如果用他维护原数组的差分数组，那么他就相当于维护的原数组，这样利用第一个性质单点查询就解决了。再就是区间修改，因为我们维护的是差分数组，所以利用性质二进行区间修改就好了。
看代码就很清楚明了了
#include<cstdio>
#include<iostream>
using namespace std;
const int N=;
int n,m,a[N],tree[N];
void read(int &x)
{
x=;int f=;char c=getchar();
while(c<''||c>'') { if(c=='-') f=-; c=getchar(); }
while(c>=''&&c<=''){ x=x*+c-''; c=getchar();}
x=x*f;
}
void add(int pos,int w)
{
while(pos<=n)
{
tree[pos]+=w;
pos+=pos&-pos;
}
return;
}
int ff(int pos)
{
int ans=;
while(pos>=)
{
ans+=tree[pos];
pos-=pos&-pos;
}
return ans;
} int main()
{
int last=;
read(n),read(m);
for(int i=,x;i<=n;++i)
{
read(x);
add(i,x-last);
last=x;
}
for(int i=,x,y,z,k;i<=m;++i)
{
read(x);
if(x==)
{
read(y),read(z),read(k);
add(y,k);
add(z+,-k);
}
else if(x==)
{
read(y);
printf("%d\n",ff(y));
}
}
return ;
}