高级数据结构-树状数组

介绍

树状数组的推导

两个基础操作

模板-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;
}

原文地址：https://blog.csdn.net/m0_69379426/article/details/144358512

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！