树状数组总结
对于树状数组，基本操作有以下两种
int sum(int x){ int ret=0; while(x>0){ ret+=C[x]; x-=lowbit(x); } return ret; }void add(int x,int d){ while(x<=n){ C[x]+=d; x+=lowbit(x); }} 对于树状数组，代码功能其实不难理解，主要是对于操作利用要灵活，选取多个习题进行练习是个不错的选择
树状数组基本操作
习题1：
- 题意：n个人，现在需要这样的三人集合：中间的人技能值处在左右两个人的技能值之间，问存在多少个这样的集合。
- 解法：设l[i]为i左边小于a[i]的人数，r[i]为大于其的人数，答案为
for i:1~n ans+=l[i]*r[i]+(i-1-l[i])*(n-i-r[i]);
重点在于对l[i]和r[i]的计算
memset(C,0,sizeof(C));for(int i=1; i<=n; i++){ l[i]=sum(a[i]-1); add(a[i],1);}memset(C,0,sizeof(C));for(int i=n; i>=1; i--){ r[i]=n-i-sum(a[i]); add(a[i],1);} 习题2：
- 题意：对于一个数列(1~n乱序)，每次把最前面的一个数放到数列最后面，求所有这样的操作中逆序数最少时是多少
- 解法：首先求出现有数列的逆序数之和ans，然后每个a[i]移至数列之尾对ans的影响为ans=ans-(n-a[i])+(a[i]-1)，枚举即可得到答案
(现有逆序数之和怎么求？)
for i:1~nans+=sum(a[i]+1); //sum(a[i])求在i之前比a[i]大的数字个数add(a[i],1);
通过前两题，可以说对树状数组的基本操作有了个认识,现在可以进行更高层次的训练
树状数组+离线处理
习题1：
题意：一串珠子，每个珠子有一个值，query(l,r)是问l到r之间珠子的值之和，同时相同的值只计数一次，如 1 2 1，query(1,3)=3
解法：
不如结合案例进行分析如下原数列为：2,3,4,3我们对所有的(n)*(n-1)/2个(l,r)区间进行推算1. (l,1) --> query(1,1)=2; 2. (l,2) --> query(1,2)=5; query(2,2)=3; 3. (l,3) --> query(1,3)=9; query(2,3)=7; query(3,3)=4;4. (1,4) --> query(1,4)=9; //注意到此处 query(2,4)=7; //注意到此处 query(3,4)=7; query(4,4)=3;
很显然，前三组数据都可以使用树状数组直接求出，只有到第四组数据的时候会出现误差，然而这样的差错在按照r按顺序排列查询是可以避免的。只要我们在新出现的数字出现时判断之前是否已经出现过，如果出现，就把之前的那个位置清空，在新的下标上加上这个数字。
Q：只将r端点进行排序，l端点出现的顺序对答案有没有影响？
Ans：没有，我们只需要计算a[r]这个数字一次就行了，更新的这个数字顶多也就是a[r]这个位置的数，对l的数字没有任何影响
sort(b+1,b+m+1,cmp1); //按r从小到大排序int q=1;for(int i=1; i<=n&&q<=m; i++){ if(book[a[i]]) add(book[a[i]],-a[i]); add(i,a[i]); book[a[i]]=i; while(b[q].r==i) { b[q].ans=sum(b[q].r)-sum(b[q].l-1); q++; }}sort(b+1,b+m+1,cmp2); //按id从小到大排序for(int i=1; i<=m; i++){ printf("%lld\n",b[i].ans);}