作用：
查询应该是res+=tr[i]
1.楼兰图腾
tr表示这个位置有多少个这个数
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+10; int n; int tr[N],a[N]; ll up[N],down[N];//up记录上升的有多少个数，down记录下降的有多少个数 int lowbit(int x)//lowbit运算 { return x&-x; } void add(int x,int c)//某个位置加一个数的操作 { for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c; } int sum(int x)//算前x个的和 { int res=0; for(int i=x;i;i-=lowbit(i)) res+=tr[i]; return res; } int main() { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); //一开始tr是0，啥也没有一个数都没有 for(int i=0;i<n;i++) { int y=a[i]; up[i]=sum(n)-sum(y);//表示目前为止，0~i位置有多少个数是大于大于y的 down[i]=sum(y-1);//表示目前为止，0~i位置有多少个数是小于y的 add(y,1);//该位置添加个y } ll res1=0,res2=0; //现在的tr是已经弄到了整个序列的数了 for(int i=0;i<n;i++) { int y=a[i]; res1+=up[i]*(ll)(sum(n)-sum(y));//答案就是左边大于y的数乘以右边大于y的数 res2+=down[i]*sum(y-1);//答案就是左边小于y的数乘以右边小于y的数 add(y,-1);//把这个数去掉，不然待会算右边会算到这个数，实际是这个数已经用过了 } printf("%lld %lld\n",res1,res2); return 0; }
2.一个简单的整数问题（差分）
把tr数组当成差分数组即可
假如[l,r]+c,则b[l]+=c,b[r+1]-=c;
假如求x的数是多少，相当于求b[x]的前缀和，然后可以直接用树状数组求用sum(x)即可
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n,m; int tr[N],a[N];//tr就是差分数列 int lowbit(int x)//lowbit运算 { return x&-x; } void add(int x,int c)//某个位置加一个数的操作 { for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c; } int sum(int x)//求前x项和 { int res=0; for(int i=x;i;i-=lowbit(i)) res+=tr[i]; return res; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) add(i,a[i]-a[i-1]);//让tr是a[i]的差分，则b[i]=a[i]-a[i-1] while(m--) { char str[2]; scanf("%s",str); if(str[0]=='Q') { int op; scanf("%d",&op); printf("%d\n",sum(op));//输出前op项和 } else { int l,r,c; scanf("%d%d%d",&l,&r,&c); add(l,c),add(r+1,-c);//差分，b[l]+=c,b[r+1]-=c } } return 0; }
3.一个简单的整数问题2（差分+分析）
弄两个树状数组，其中一个是差分数组b[i]，另一个是i*b[i]
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; int n,m; int a[N]; ll tr1[N],tr2[N];//tr1记录的是b[i],tr2是i*b[i] int lowbit(int x)//lowbit运算 { return x&-x; } void add(ll tr[],int x,ll c)//某个树状数组的加数 { for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c; } ll sum(ll tr[],int x)//某个树状数组的求前缀和 { ll res=0; for(int i=x;i;i-=lowbit(i)) res+=tr[i]; return res; } ll ans(int x)//求总数组的前x项的和 { return sum(tr1,x)*(x+1)-sum(tr2,x); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) add(tr1,i,a[i]-a[i-1]),add(tr2,i,(ll)i*(a[i]-a[i-1]));//初始化初始值 while(m--) { char op[2]; int l,r,c; scanf("%s%d%d",op,&l,&r); if(op[0]=='Q') printf("%lld\n",ans(r)-ans(l-1));//求l~r的和，也就是1~r的和减去1~l的和 else { scanf("%d",&c); //b[l]+=c add(tr1,l,c),add(tr2,l,l*c); //b[r+1]-=c; add(tr1,r+1,-c),add(tr2,r+1,(ll)-c*(r+1)); } } return 0; }
4.谜一样的牛（二分查找）
思路：从n往1看，每次给剩余的数里面第a[i]+1小的数，然后把这个数删掉，一直这样操作即可
找第a[i]+1小的数:
1.把每个数初始值为1，表明这个数还没用过，每个前缀和表明了当前数是第几小的数
2.二分查找第a[i]+1小的数，因为每个数的前缀和是递增的可以二分
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n; int a[N],tr[N],ans[N]; int lowbit(int x) { return x&-x; } void add(int x,int c) { for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c; } int sum(int x) { int res=0; for(int i=x;i;i-=lowbit(i)) res+=tr[i]; return res; } int main() { scanf("%d",&n); for(int i=2;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) add(i,1);//初始化初始值,让每个数都为1，表明没有用过 for(int i=n;i;i--) { int b=a[i]+1;//找第a[i]+1小的数 int l=1,r=n; while(l<r)//二分 { int mid=l+r>>1; if(sum(mid)>=b) r=mid;//假如前缀和大了，说明当前数不是第b小的数 else l=mid+1; } ans[i]=l;//让答案等于当前找到的第b小的数 add(l,-1);//把当前数删除，因为已经用过了 } for(int i=1;i<=n;i++) printf("%d\n",ans[i]); return 0; }
