问：你这个乡村学校的小学生，为什么要学劼劼劼呢？
答：因为窝一下做了太多的树状数组，懒得一篇一篇写了。
问：既然线段树可以代替树状数组，那么为什么要树状数组呢？
答：树状数组好写啊Orz。
问：那我可以不看冗长的介绍过程吗？
答：如果机房的门要关了或者你急着要泡妹子，请跳至最后一目。
【简介】
首先普通的一维树状数组就不说了，如果你不知道，戳这。
那么窝萌阔以看到：普通的树状数组支持单点修改、片段和。
显然树状数组是解决逆序对问题的最好方法。
某大神表示阔以用树状数组来维护区间最值，不明觉厉~
inline void init()
{
CLR(arr,0);
for(int i=1;i<=N;++i)
for(int j=i;j<=N&&arr[j]<num[i];j+=lowbit(j))
arr[j]=num[i];
}
inline int query(int L,int R)
{
int res=0;
for(--L;L<R;){
if(R-lowbit(R)>=L){res=max(res,arr[R]);R-=lowbit(R);}
else{res=max(res,num[R]);--R;}
}
return res;
}
inline void update(int x,int val)
{
int ori=num[x];
num[x]=val;
if(val>=ori)
for(int i=x;i<=N&&arr[i]<val;i+=lowbit(i))
arr[i]=val;
else{
for(int i=x;i<=N&&arr[i]==ori;i+=lowbit(i))
{
arr[i]=val;
for(int j=lowbit(i)>>1;j;j>>=1)
arr[i]=max(arr[i],arr[i-j]);
}
}
}
那么树状数组可不可以支持区间修改呢？
让窝萌先来解决一个子问题：维护一个序列，支持区间修改、单点求值。
那么差分，令d[i]=a[i]-a[i-1]，d[1]=a[1]，那么显然[tex]a[i] = \sum\limits_{j = 1}^n {d[j]}[/tex]
修改区间[l,r]，则可以通过前缀和得到：d[l]+=k,d[r+1]-=k。
那么要求区间和怎么办呢？
通过简单的推导可以得到：
[tex]\sum\limits_{i = 1}^x {a[i]} = \sum\limits_{i = 1}^x {d[i]*(x - i + 1) = (x + 1)*\sum\limits_{i = 1}^x {d[i]} - \sum\limits_{i = 1}^x {d[i]*i} }[/tex]
那么再开一个树状数组来维护d[i]*i就阔以辣！
接着看二维树状数组。
显然根据树状数组的定义再加一维就阔以了。
即令tree[i][j]为矩阵[i-lowbit(i)+1,j-lowbit(j)+1]~[i,j]的片段和。
对于二维树状数组的区间修改和求和，可以通过二维前缀和的性质推出。
这里的d[i]有另一个定义，表示i~n这一段的都加上d[i]。
那么扩展到二维，d[i][j]表示矩阵[i,j]~[n,m]的都加上d[i][j]。
修改矩阵[x1,y1]~[x2,y2]，那么d[x1][y1]+=k,d[x1][y2+1]-=k,d[x2+1][y1]-=k,d[x2+1][y2+1]+=k。
求[1,1]~[x,y]，就是p-q。
[tex]p = (x + 1)(y + 1)\sum\limits_{i = 1}^x {\sum\limits_{j = 1}^y {a[i][j]} } + \sum\limits_{i = 1}^x {\sum\limits_{j = 1}^y {a[i][j]*i*j} }[/tex]
[tex]q = (x + 1)\sum\limits_{i = 1}^x {\sum\limits_{j = 1}^y {a[i][j]*j + (y + 1)\sum\limits_{i = 1}^x {\sum\limits_{j = 1}^y {a[i][j]} } } } *i[/tex]
[tex]
显然我讲的很不详细，所以戳这
（悄悄地告诉你其实窝前面也是抄的论文）
【例题】
BZOJ2789
首先看到一个贪心性质，即第一个串中第k次出现的某个字母对应的一定是第二个中第k次出现的。
那么求个逆序对就阔以了。
BZOJ2743
先求出每个元素下一个与它相同的是第几个。
显然如果[l,r]中有两个同样的元素，该元素的编号为i>=l，则next[i]<=r就阔以了。
那么对询问进行离线操作，其余的还是程序说得更清楚，所以开始看程序吧。
BZOJ1452
对于每种颜色开个二维树状数组就水过了。。。
BZOJ3132
论文题，看完了绝逼会做。
BZOJ3038
显然发现了一个神奇的性质：一个数只要开根了7次后就会变成1，然后就不变了。
那么就用并查集维护变成1的区间不用改了，然后用树状数组维护整个序列。
BZOJ1106
如果两个相同的数间有x个未消掉的数，那么就需要交换x次。
那么只要知道区间内只出现过一次的数的个数就阔以啦！
【Codes】
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=1000010;
int n,i;
long long ans;
char a[M],b[M];
int c[M],tree[M],now[30];
int q[27][M];
int query(int x){
int ans=0;
for (int i=x;i>0;i-=i&-i)ans+=tree[i];
return ans;
}
void update(int x){
for (int i=x;i<=n;i+=i&-i)tree[i]++;
}
int main(){
scanf("%d",&n);
scanf("%s",a+1);
scanf("%s",b+1);
for (i=1;i<=n;i++)q[a[i]-'A'][++q[a[i]-'A'][0]]=i;
for (i=1;i<=n;i++)c[i]=q[b[i]-'A'][++now[b[i]-'A']];
for (i=n;i>=1;i--){
ans+=query(c[i]);
update(c[i]);
}
printf("%lld\n",ans);
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=1000010;
int n,m,p,i,l;
int a[M],now[M],next[M],ans[M],tree[M];
struct shit{int l,r,id;}q[M];
int cmp(shit a,shit b){return a.l<b.l;}
int query(int x){
int ans=0;
for (int i=x;i>0;i-=i&-i)ans+=tree[i];
return ans;
}
void update(int x,int p){
for (int i=x;i<=n;i+=i&-i)tree[i]+=p;
}
int main(){
scanf("%d%d%d",&n,&p,&m);
for (i=1;i<=n;i++)scanf("%d",&a[i]);
for (i=n;i>0;i--)next[i]=now[a[i]],now[a[i]]=i;
for (i=1;i<=p;i++)if (next[now[i]])update(next[now[i]],1);
for (i=1;i<=m;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
sort(q+1,q+m+1,cmp);
l=1;
for (i=1;i<=m;i++){
while (l<q[i].l){
if (next[l])update(next[l],-1);
if (next[next[l]])update(next[next[l]],1);
l++;
}
ans[q[i].id]=query(q[i].r)-query(q[i].l-1);
}
for (i=1;i<=m;i++)printf("%d\n",ans[i]);
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,i,j,opt,q,x,y,ch,x1,x2,y1,y2;
int a[310][310];
int tree[110][310][310];
void update(int opt,int x,int y,int p){
for (int i=x;i<=n;i+=i&-i)
for (int j=y;j<=m;j+=j&-j)
tree[opt][i][j]+=p;
}
int query(int opt,int x,int y){
int ans=0;
for (int i=x;i;i-=i&-i)
for (int j=y;j;j-=j&-j)
ans+=tree[opt][i][j];
return ans;
}
int main(){
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
for (j=1;j<=m;j++){
scanf("%d",&a[i][j]);
update(a[i][j],i,j,1);
}
scanf("%d",&q);
while (q--){
scanf("%d",&opt);
if (opt==1){
scanf("%d%d%d",&x,&y,&ch);
update(a[x][y],x,y,-1);
a[x][y]=ch;
update(a[x][y],x,y,1);
}else{
scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&ch);
printf("%d\n",query(ch,x2,y2)-query(ch,x1-1,y2)-query(ch,x2,y1-1)+query(ch,x1-1,y1-1));
}
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char s[10];
int n,m,x1,x2,y1,y2,ch;
int tree[2100][2100][4];
void update(int x,int y,int p){
for (int i=x;i<=n;i+=i&-i)
for (int j=y;j<=m;j+=j&-j){
tree[i][j][0]+=p;
tree[i][j][1]+=p*x;
tree[i][j][2]+=p*y;
tree[i][j][3]+=p*x*y;
}
}
int query(int x,int y){
int ans=0;
for (int i=x;i;i-=i&-i)
for (int j=y;j;j-=j&-j)
ans=ans+tree[i][j][0]*(x+1)*(y+1)-tree[i][j][1]*(y+1)-tree[i][j][2]*(x+1)+tree[i][j][3];
return ans;
}
int main(){
scanf("%s",s);
scanf("%d%d",&n,&m);
while (scanf("%s",s)!=EOF){
if (s[0]=='L'){
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&ch);
update(x1,y1,ch);
update(x2+1,y1,-ch);
update(x1,y2+1,-ch);
update(x2+1,y2+1,ch);
}else{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
printf("%d\n",query(x2,y2)-query(x1-1,y2)-query(x2,y1-1)+query(x1-1,y1-1));
}
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
typedef long long ll;
using namespace std;
int n,m,i,opt,x,y;
int f[100010];
ll a[100010],tree[100010];
int search(int x){
if (!f[x])f[x]=x;
if (f[x]!=x)f[x]=search(f[x]);
return f[x];
}
ll query(int x){
ll ans=0;
for (int i=x;i;i-=i&-i)ans+=tree[i];
return ans;
}
void update(int x,ll y){
for (int i=x;i<=n;i+=i&-i)tree[i]+=y;
}
void solve(int x,int y){
for (int i=search(x);i<=y;i=search(i+1)){
ll tmp=(ll)sqrt(a[i]);
update(i,tmp-a[i]);
a[i]=tmp;
if (a[i]<=1)f[i]=search(i+1);
}
}
int main(){
scanf("%d",&n);
for (i=1;i<=n;i++){
scanf("%lld",&a[i]);
if (a[i]<=1)f[i]=i+1;
update(i,a[i]);
}
scanf("%d",&m);
for (i=1;i<=m;i++){
scanf("%d%d%d",&opt,&x,&y);
if (x>y)swap(x,y);
if (!opt)solve(x,y);else printf("%lld\n",query(y)-query(x-1));
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,i,ans;
int a[100010],tree[100010],pre[100010];
void update(int x,int y){
for (int i=x;i<=2*n;i+=i&-i)tree[i]+=y;
}
int query(int x){
int ans=0;
for (int i=x;i;i-=i&-i)ans+=tree[i];
return ans;
}
int main(){
scanf("%d",&n);
for (i=1;i<=2*n;i++)scanf("%d",&a[i]);
for (i=1;i<=2*n;i++){
if (!pre[a[i]])pre[a[i]]=i,update(i,1);
else{
ans+=query(i)-query(pre[a[i]]);
update(pre[a[i]],-1);
}
}
printf("%d\n",ans);
}
