高级数据结构—树状数组

引入问题：

给出一个长度为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;
}