高级数据结构-树状数组

介绍

树状数组的推导

两个基础操作

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