线段树和树状数组在很多时候都可以用来处理相同的问题，特别是在用来进行RMQ离线处理时候两者各有所长，故放在一起整理。
首先是线段树，线段树除了最后一层子节点整体是一颗标准的完全树，所以有着许多很有趣的特点，在区域搜索、区域数值增改中有着很大的优势，先上一道水题
poj3264 线段树
题意是对给出的Q次访问求出访问区间中数值的最大差值，正好与线段树的区间搜索相符。
本意是想用RMQ离线处理一下，但是因为本身不存在增改，离线处理也不会增加多少效率，所以就直接写了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <list>
using namespace std;
#define N 50005
#define Q 200005
int n,q;
int mi,ma;
struct tree
{
int l,r;
int mi,ma;
}s[Q * 2];
int c[N];
void update(int wei)
{
int l = s[wei].l;
int r = s[wei].r;
if(l == r)
{
s[wei].ma = s[wei].mi = c[l];
return;
}
int ls = wei * 2;
int rs = ls + 1;
int mid = (l + r) / 2;
s[ls].l = l;
s[ls].r = mid;
update(ls);
s[rs].l = mid + 1;
s[rs].r = r;
update(rs);
s[wei].ma = max(s[ls].ma,s[rs].ma);
s[wei].mi = min(s[ls].mi,s[rs].mi);
}
void cal(int wei,int l,int r)
{
if(l == s[wei].l && r == s[wei].r)
{
mi = min(mi,s[wei].mi);
ma = max(ma,s[wei].ma);
return;
}
int mid = (s[wei].l + s[wei].r) / 2;
if(mid >= r) cal(wei * 2,l,r);
else if(mid < l) cal(wei*2+1,l,r);
else
{
cal(wei*2,l,mid);
cal(wei*2+1,mid+1,r);
}
}
void out(int a,int b)
{
mi = 1000005;
ma = 0;
cal(1,a,b);
printf("%d\n",ma - mi);
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%d",&c[i]);
}
s[1].l = 1;
s[1].r = n;
update(1);
int a,b;
for(int i=0;i<q;i++)
{
scanf("%d%d",&a,&b);
out(a,b);
}
return 0;
}
多校第四场hdu4638Group 线段树 + RMQ
题意是对给出访问求区域内能成立的组的个数（相邻点数之差为1可以加进一个组、一个数与相邻组存在差为1数的时候可以加入这个组）
因为组的情况不定，每次询问都要对线段树内的内容更新，这时就需要RMQ离线处理了，按照左位置或者右位置排序后按序处理整体输出
因为这样子写出出来好多变量与函数（有建树用的和离线运算一起更新所需要的变量与函数，按我的写法至少需要四个函数与十多个变量）写到后来很容易就乱了，以后需要好好研究怎么定义变量名以实现程序内容的清晰化。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <list>
#include <map>
using namespace std;
#define N 100005
struct tree
{
int l,r;
int ans;
}s[N * 4];
int c[N];
int wei[N];
int n,m;
struct node
{
int l,r;
int wei;
}sum[N];
int ans[N];
void update(int w)
{
s[w].ans = 0;
int l = s[w].l;
int r = s[w].r;
if(l == r) return;
int ls = w * 2;
int rs = ls + 1;
int mid = (l + r) / 2;
s[ls].l = l;
s[ls].r = mid;
update(ls);
s[rs].l = mid + 1;
s[rs].r = r;
update(rs);
}
bool cmp(node x,node y)
{
return x.r < y.r;
}
void cal(int w,int l,int r,int shu)
{
if(l > r) return;
if(s[w].l == l&&s[w].r == r)
{
s[w].ans += shu;
return;
}
int ls = w * 2;
int rs = ls + 1;
int mid = (s[w].l + s[w].r) / 2;
s[ls].ans += s[w].ans;
s[rs].ans += s[w].ans;
s[w].ans = 0;
if(l > mid) cal(rs,l,r,shu);
else if(r <= mid) cal(ls,l,r,shu);
else
{
cal(ls,l,mid,shu);
cal(rs,mid+1,r,shu);
}
}
int add(int w,int l)
{
if(s[w].l == s[w].r) return s[w].ans;
int ls = w * 2;
int rs = ls + 1;
int mid = (s[w].l + s[w].r) / 2;
s[ls].ans += s[w].ans;
s[rs].ans += s[w].ans;
s[w].ans = 0;
if(l > mid) return add(rs,l);
else return add(ls,l);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
memset(wei,0,sizeof(wei));
for(int i=1;i<=n;i++)
{
scanf("%d",&c[i]);
}
s[1].l = 1;
s[1].r = m;
update(1);
for(int i=0;i<m;i++)
{
scanf("%d%d",&sum[i].l,&sum[i].r);
sum[i].wei = i;
}
sort(sum,sum + m,cmp);
int i = 1;
int j = 0;
while(j < m&&i <= n)
{
int x = c[i];
cal(1,1,i-1,1);
if(wei[x - 1]) cal(1,1,wei[x - 1],-1);
if(wei[x + 1]) cal(1,1,wei[x + 1],-1);
wei[x] = i;
cal(1,i,i,1);
while(j < m && sum[j].r <= i)
{
ans[sum[j].wei] = add(1,sum[j].l);
j++;
}
i++;
}
for(int i=0;i<m;i++)
{
printf("%d\n",ans[i]);
}
}
return 0;
}
除去二维的，上面的就是线段树大多数的基本用法了，之后说说树状数组。
树状数组是基于二进制数做出来的数据访问的优化方法，所以每次定义的时候必须从1开始（线段树如果想用齐满树的特征来省变量也需要从1开始）
如果说线段树最大的优势是区间访问与更新，那树状数组最大的优势就是对单点的访问与更新。
同样以hdu4638Group为例，只要把中间的线段树部分改成了树状数组就可以了。
并且因为实际上这题都是对点更新所以时间效率还要高一点，但是和线段树有着同一个问题（树状数组有固有的lowbit函数与更新的update函数，与线段树的的建树update/maketree函数以及更新的cal/update正好凑成一对）函数变量很多，写的很晕。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <list>
using namespace std;
#define N 100005
int n,m;
int a[N];
int s[N];
int num[N];
int ans[N];
struct node
{
int l,r;
int wei;
}c[N];
int lowbit(int x)
{
return x&(-x);
}
void update(int wei,int shu)
{
while(wei <= n)
{
s[wei] += shu;
wei += lowbit(wei);
}
}
int sum(int wei)
{
int ans = 0;
int i = wei;
while(i > 0)
{
ans += s[i];
i -= lowbit(i);
}
return ans;
}
bool cmp(node x,node y)
{
return x.l < y.l;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
num[a[i]] = i;
}
num[0] = num[n+1] = N;
memset(s,0,sizeof(s));
for(int i=1;i<=n;i++)
{
if(i < num[a[i] - 1] && i < num[a[i] + 1]) update(i,1);
if(i > num[a[i] - 1] && i > num[a[i] + 1]) update(i,-1);
}
int l,r;
for(int i=0;i<m;i++)
{
scanf("%d%d",&l,&r);
c[i].l = l;
c[i].r = r;
c[i].wei = i;
}
sort(c,c+m,cmp);
int i = 1;
int j = 0;
while(j < m)
{
//cout<<j<<' '<<i<<endl;
while(i <= n && i < c[j].l)
{
//cout<<i<<'i'<<endl;
if(i > num[a[i]-1] && i > num[a[i]+1]) update(i,-1);
else if(i < num[a[i]-1] && i < num[a[i]+1])
{
l = min(num[a[i]-1],num[a[i]+1]);
r = max(num[a[i]-1],num[a[i]+1]);
update(i,-1);
update(l,1);
update(r,1);
}
else if(i < num[a[i]-1])
{
update(i,-1);
update(num[a[i]-1],1);
}
else
{
update(i,-1);
update(num[a[i]+1],1);
}
i++;
}
while( j < m && c[j].l <= i)
{
//cout<<j<<'j';
ans[c[j].wei]= sum(c[j].r);
j++;
}
}
for(int i=0;i<m;i++)
{
printf("%d\n",ans[i]);
}
}
return 0;
}
总的来说，树状数组能处理的问题基本线段树都能处理，而线段树能处理的问题范围要比树状数组广，很多时候两者时间仅仅只是效率差而已，择优而用很重要~~^_^~~