樹狀數(shù)組適用范圍：給定區(qū)間稍浆，求最值，求和摇天，區(qū)間單點修改粹湃。
與RMQ不同的是，RMQ一般只用作區(qū)間求最值泉坐。但在最值方面RMQ更加便捷为鳄。
樹狀數(shù)組
從圖上可以看出要找到c[i]的父節(jié)點只要用i+x（x為i轉(zhuǎn)化為二進制從右起第一個出現(xiàn)1的位置）就可以了
尋找x可以通過lowbit函數(shù)，即通過計算機補碼的巧用腕让，x=i&（-i）
int lowbit(int x)
{
return x&(-x);
}
而每一個父節(jié)點存儲的數(shù)據(jù)都是下面所有子節(jié)點的全部信息孤钦。對子節(jié)點修改就必定會對其所有的父節(jié)點進行更新，父節(jié)點c[i]下標的查找如下：
void update(int i, int x)
{
while(i<=n)
{
c[i]+=x;
i+=lowbit(i);//更新父節(jié)點
}
}
對于查找1~i的和纯丸、最大值偏形、最小值可以表示為：
int sum(int i)
{
int res=0;
while(i>0)
{
res+=c[i];
i-=lowbit(i);
}
return res;
}
典型例題（模版）：
HDU - 1166
對一個區(qū)域的數(shù)列進行查找、修改
#include<cstdio>
#include<cstring>
using namespace std;
int c[50005];
int n;
int lowbit(int x)
{
return x&(-x);
}
void update(int i, int x)
{
while(i<=n)
{
c[i]+=x;
i+=lowbit(i);//更新父節(jié)點
}
}
int sum(int i)
{
int res=0;
while(i>0)
{
res+=c[i];
i-=lowbit(i);
}
return res;
}
int main()
{
int T, cnt;
scanf("%d", &T);
for(cnt=1; cnt<=T; cnt++)
{
int i, temp;
char op[10];
memset(c,0,sizeof(c));
scanf("%d", &n);
for(i=1 ;i<=n; i++)
{
scanf("%d", &temp);
update(i, temp);
}
printf("Case %d:\n", cnt);
while(~scanf("%s", op))
{
int l, r, k;
if(!strcmp(op,"End")) break;
if(!strcmp(op,"Query"))
{
scanf("%d%d", &l, &r);
printf("%d\n", sum(r)-sum(l-1));
}
if(!strcmp(op,"Add"))
{
scanf("%d%d", &k, &temp);
update(k, temp);
}
if(!strcmp(op,"Sub"))
{
scanf("%d%d", &k, &temp);
update(k, -temp);
}
}
}
return 0;
}
例題：POJ - 3928
題目大意：在數(shù)列X中找到a觉鼻、b俊扭、c
滿足a<b<c和X[a]<X[b]<X[c]
思路：求取前綴和和后綴和的問題，update(X[i], 1);再getsum（）即可
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long int
const int maxn = 1e5+7;
const int max_num = 1e5;
int a[maxn];
ll c[maxn];
int pos_west[maxn], pos_east[maxn], neg_west[maxn], neg_east[maxn];
int lowbit(int x)
{
return x&(-x);
}
void update(int i, int p)
{
while(i<=max_num)
{
c[i]+=p;
i+=lowbit(i);
}
}
ll getsum(int i)
{
int res=0;
while(i>0)
{
res+=c[i];
i-=lowbit(i);
}
return res;
}
void init()
{
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
memset(pos_west,0,sizeof(pos_west));
memset(pos_east,0,sizeof(pos_east));
memset(neg_west,0,sizeof(neg_west));
memset(neg_east,0,sizeof(neg_east));
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
int i, n;
ll sum=0;
scanf("%d", &n);
init();
for(i=1; i<=n; i++)
{
scanf("%d", &a[i]);
update(a[i],1);
pos_west[i]=getsum(a[i]-1);
pos_east[i]=getsum(max_num)-getsum(a[i]);
}
memset(c,0,sizeof(c));
for(i=n; i>0; i--)
{
update(a[i],1);
neg_west[i]=getsum(a[i]-1);
neg_east[i]=getsum(max_num)-getsum(a[i]);
}
for(i=1; i<=n; i++)
{
sum+=pos_west[i]*neg_east[i]+neg_west[i]*pos_east[i];
}
printf("%I64d\n", sum);
}
return 0;
}
注：此方法還可以用來求取逆序數(shù)Ｗ钩隆Ｈ蟆！
例題：HDU - 1556
給定區(qū)間仇矾，每次在這個區(qū)間加1庸蔼，求每個點一共加了多少次1
思路：前綴和思想，如圖
前綴和
#include<cstdio>
#include<cstring>
using namespace std;
int c[100005];
int n;
int lowbit(int x)
{
return x&(-x);
}
void update(int i, int p)
{
while(i<=n)
{
c[i]+=p;
i+=lowbit(i);
}
}
int getsum(int i)
{
int res=0;
while(i>0)
{
res+=c[i];
i-=lowbit(i);
}
return res;
}
int main()
{
while(~scanf("%d", &n)&&n)
{
int a, b;
memset(c,0,sizeof(c));
for(int i=1; i<=n; i++)
{
scanf("%d%d", &a, &b);
update(a, 1);
update(b+1, -1);
}
for(int i=1; i<=n; i++)
{
if(i!=1) printf(" ");
printf("%d", getsum(i));
}
printf("\n");
}
return 0;
}
