引入问题：
给出一个长度为n的数组，完成以下两种操作：
1. 将第i个数加上k
2. 输出区间[i,j]内每个数的和
朴素算法：
单点修改：O( 1 )
区间查询：O( n )
使用树状数组：
单点修改：O( logn )
区间查询：O( logn )
前置知识：
lowbit()
运算：非负整数x在二进制表示下最低位1及其后面的0构成的数值。
如lowbit（12）= 1100 = 4
函数实现：
int lowbit(int x){
return x&(-x);
}树状数组思想：
树状数组的主要思想就是利用树结构维护“前缀和”。
对于一个序列，对其建立如下树形结构：
1.每个结点t[x]保存以x为根的子树中叶结点值的和
2.每个结点覆盖的长度为lowbit(x)
3.t[x]结点的父结点为t[x + lowbit(x)]
4.树的深度为log2n+1
树状数组操作：
add(x, k)表示将序列中第x个数加上k。
在整棵树上维护这个值，需要一层一层向上找到父结点，并将这些结点上的t[x]值都加上k，这样保证计算区间和时的结果正确。
void add(int x, int k)
{
for(int i = x; i <= n; i += lowbit(i))
t[i] += k;
}ask(x)表示将查询序列前x个数的和
以ask(7)为例：
查询这个点的前缀和，需要从这个点向左上找到上一个结点，将加上其结点的值。向左上找到上一个结点，只需要将下标 x -= lowbit(x)，例如 7 - lowbit(7) = 6
int ask(int x)
{
int sum = 0;
for(int i = x; i; i -= lowbit(i))
sum += t[i];
return sum;
}例题：
楼兰图腾
题目链接：楼兰图腾
从左向右依次遍历每个数a[i]，使用树状数组统计在i位置之前所有比a[i]大的数的个数、以及比a[i]小的数的个数。
统计完成后，将a[i]加入到树状数组。
从右向左依次遍历每个数a[i]，使用树状数组统计在i位置之后所有比a[i]大的数的个数、以及比a[i]小的数的个数。
统计完成后，将a[i]加入到树状数组。
代码附上：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+5;
int tr[N];
int low[N],great[N];
int a[N];
int 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;
}
return;
}
int ask(int x){
int res=0;
for(int i=x;i>=1;i-=lowbit(i)){
res+=tr[i];
}
return res;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){//记录i点左边的信息
int y=a[i];
low[i]=ask(y-1);//low[i]记录左边[1,y-1]区间的数字个数
great[i]=ask(n)-ask(y);//great[i]记录左边[y+1,n]区间的数字个数
add(y,1);//加入树状数组中，出现一次+1
}
memset(tr,0,sizeof(tr));//初始化
int ans1=0,ans2=0;
for(int i=n;i>=1;i--){//记录i点右边的信息
int y=a[i];
ans2+=low[i]*ask(y-1);//乘法原理
ans1+=great[i]*(ask(n)-ask(y-1));
add(y,1);
}
cout<<ans1<<" "<<ans2<<"\n";
return 0;
}一个简单的整数问题
题目链接：一个简单的整数问题
区间修改 + 求单点
那么这道题目可以采用差分的方法去做，在上一道题目中我们求的是区间和，采用前缀和的思想去做，那么这里我们可以把单点a[i]看成前缀和，因为a[i]=差分和。
首先我们要先建差分数组：
for(int i=1;i<=n;i++){
add(i,a[i]-a[i-1]);
}那么接下来的情况就跟第一题一样了
代码附上：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N =1e5+5;
int a[N],tr[N],low[N],great[N];
int n,q;
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;
}
return;
}
int ask(int x){
int res=0;
for(int i=x;i>=1;i-=lowbit(i)){
res+=tr[i];
}
return res;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
add(i,a[i]-a[i-1]);
}
while(q--){
char op;cin>>op;
if(op=='C'){
int l,r,d;cin>>l>>r>>d;
add(l,d);
add(r+1,-d);
}
else if(op=='Q'){
int l;cin>>l;
cout<<ask(l)<<"\n";
}
}
return 0;
}一个简单的整数问题2
题目链接：一个简单的整数问题2
区间查询+区间修改
直接上图：
所以这道题目我们需要维护两个树状数组，一个是d[i]，另一个是i*d[i]。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
int n,m;
int a[N];
int tr[N],tr2[N];
//tr[]数组是原始数组的差分数组d[i]的树状数组
//tr2[]数组是原始数组的差分数组乘以i即i*d[i]的树状数组
int lowbit(int x){
return x&-x;
}
void add1(int x,int c){
for(int i=x;i<=n;i+=lowbit(i)){
tr[i]+=c;
}
return;
}
void add2(int x,int c){
for(int i=x;i<=n;i+=lowbit(i)){
tr2[i]+=c;
}
return;
}
int ask1(int x){
int res=0;
for(int i=x;i>=1;i-=lowbit(i)){
res+=tr[i];
}
return res;
}
int ask2(int x){
int res=0;
for(int i=x;i>=1;i-=lowbit(i)){
res+=tr2[i];
}
return res;
}
int get_sum(int x){//最后一步的推导
return ask1(x)*(x+1)-ask2(x);
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
memset(tr2,0,sizeof(tr2));
memset(tr,0,sizeof(tr));
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
int b=a[i]-a[i-1];
add1(i,b);
add2(i,b*i);
}
while(m--){
char op;cin>>op;
if(op=='Q'){
int l,r;cin>>l>>r;
cout<<get_sum(r)-get_sum(l-1)<<"\n";
}
else if(op=='C'){
int l,r,d;cin>>l>>r>>d;
add1(l,d),add1(r+1,-d);
add2(l,l*d),add2(r+1,(r+1)*(-d));
}
}
return 0;
}谜一样的牛
题目链接：谜一样的牛
仅仅根据题目的信息，很难找出他们之间的高度关系。面对这种题目，我们可以从边界去思考，（正着不行就反着来），从最后一头牛看，最后一头牛的a[i]表示前i头牛有x个比它矮的，那么也就意味着它排第x+1位，那么从倒数第二头牛来看，前面有y头比它矮的，那最后一头牛可能比它高也可能比它矮，因此，对于倒数第二头牛而言，它应该在除去上述x+1的区间[1,n]中，选取A(n−1)+1小的数。其他的牛以此类推。
假如建立一个全部元素为1的数列，某个位置的数为1代表这个高度还不知道是哪头牛的，那么就用树状数组维护该数列的前缀和，若某个位置的前缀和等于A(i)+1此时的下标就是要找的数。选择这个数后，将相应位置的1置0.可以二分这个位置。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
int a[N],ans[N],tr[N];
int 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;
}
return;
}
int ask(int x){
int res=0;
for(int i=x;i>=1;i-=lowbit(i)){
res+=tr[i];
}
return res;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
a[1]=0;
for(int i=2;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)tr[i]=lowbit(i);//初始化
for(int i=n;i>=1;i--){//从后往前枚举
int k=a[i]+1;//找剩余的牛中高度排第k
int l=1,r=n;
while(l<r){
int mid=(l+r)/2;
if(ask(mid)>=k)r=mid;
else l=mid+1;
}
ans[i]=r;
add(r,-1);//高度排第r的牛去掉
}
for(int i=1;i<=n;i++){
cout<<ans[i]<<"\n";
}
return 0;
}
