高级数据结构-树状数组

介绍

树状数组的推导

两个基础操作

模板-acwing795. 前缀和

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;
int c[N]; 

int lowbit(int x){
	return x & -x;
}

int query(int x){
	int ans = 0;
	for(; x; x -= lowbit(x)) ans += c[x];
	return ans;
}

void add(int x,int y){
	for(; x <= N; x += lowbit(x)) c[x] += y;
}

int main(){
	int n,m; scanf("%d%d",&n,&m);
	for(int i = 1; i <= n; i++){
		int num; scanf("%d",&num);
		add(i,num);
	}
	while(m--){
		int l,r; scanf("%d%d",&l,&r);
		printf("%d\n",query(r)-query(l-1));
	}
	return 0;
} 

模板-acwing5910. 求逆序对

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 1e6+10;
LL c[N],a[N];

int lowbit(int x)  // 返回末尾的1
{
    return x & -x;
}

LL query(int x){
    LL ans = 0;
    for(; x; x -= lowbit(x)) ans += c[x];
    return ans;
}

void add(int x,int y){
    for(; x <= N; x += lowbit(x)) c[x] += y;
}

int main()
{
    LL ans = 0;
    int n; scanf("%d",&n);
    for(int i = 1; i <= n; i++){
        scanf("%d",&a[i]);
    }
    //倒序扫描，找值比当前这个数小但是先进入树状数组的数，即1-（a[i]-1）的和
    for(int i = n; i >= 1; i--){
        ans += query(a[i]-1)-query(0);
        add(a[i],1);
    }
    printf("%lld\n",ans);
    return 0;
}