好难的数据结构啊。
今天刚学的树状数组，于是决定水一发算法笔记。
话不所说，让我们开始走进树状数组的世界吧。
先推荐 一篇文章，绝对可以好好看看。
众所周知，树状数组是一种修改和查询的时间复杂度都为 \(O(log_2n)\) 的一种数据结构。
它的本质是一个数组（而非一棵树），所以无需建树。
而它的基本用途是维护一个序列的前缀和（不知道的自行百度），从而进行区间查询。
那么它和线段树的区别是什么呢，请看下列解释：
A：同学，你知道线段树和树状数组的区别吗？
B：这么跟你说吧，树状数组有的功能线段树都有，所以线段树的应用范围广泛很多。
A：那有树状数组干什么。
B：别急，树状数组还是有好处的，比线段树省空间，代码复杂度比线段树小，可以扩展到多维情况。
A：但是我还是可以用线段树解决一切呀。
B：空间小的情况下只能用树状数组，而且还有更重要的一点。
A：？？？
B：高精知道吧，你完全可以用高精加去解决 \(1+1\) 等于几的问题，但是所有人都会直接加。
A：这和我的问题有什么关系？
B：树状数组就是简单的加法，而线段树就相当于高精。（高精时间长，空间大，码量大）
A：哦~，所以树状数组只是基础知识，只是为线段树做铺垫的。
B：也不能这么说，在能用树状数组的时候就尽量用它，其他的还是根据具体情况而定。
好的，既然你已经懂了，那就让我们正式进入树状数组的学习吧。??
先看一张图：（这图来自哪里你懂的）
对于序列 \(a[]\) （即黄色的部分），我们建立一个数组 \(c[]\) 用来保存区间 \([x-lowbit(x)+1,x]\) 中所有数的和。
那么显然：
\[c[x]=\sum_{i=x-lowbit(x)+1}^{x} a[i]\]
过于简单，不进行讲述。
然后我们就有了一下两个操作。
void add(int x,int k){
while(x<=n){
tree[x]+=k;
x+=lowbit(x);
}
}int ask(int x){
int ans=0;
while(x>=1){
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
#define N 2000010
using namespace std;
int n,m,tree[N];
int lowbit(int x){
return x & (-x);
}
void add(int x,int k){
while(x<=n){
tree[x]+=k;
x+=lowbit(x);
}
}
int ask(int x){
int ans=0;
while(x>=1){
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
int main(){
scanf("%d %d",&n,&m);
int a;
for(int i=1;i<=n;i++){
scanf("%d",&a);
add(i,a);
}
int flag,x,y;
for(int i=1;i<=m;i++){
scanf("%d %d %d",&flag,&x,&y);
if(flag==1){
add(x,y);
}
else{
int l=ask(x-1);
int r=ask(y);
printf("%d\n",r-l);
}
}
return 0;
}来介绍一下差分。
设数组 \(a[]={1,6,8,5,10}\)，那么差分数组 \(b[]={1,5,2,-3,5}\)。
也就是说 \(b[i]=a[i]-a[i-1] (a[0]=0)\)，那么 \(a[i]=b[1]+....+b[i]\) (这个很好证的)。
假如区间 \([2,4]\) 都加上 \(2\)的话，\(a\) 数组变为 \(a[]={1,8,10,7,10}\)，\(b\) 数组变为 \(b={1,7,2,-3,3}\)。
发现，\(b\) 数组只有 \(b[2]\) 和 \(b[5]\) 变了，因为区间 \([2,4]\) 是同时加上 \(2\) 的,所以在区间内 \(b[i]-b[i-1]\) 是不变的。
所以对区间 \([x,y]\) 进行修改,只用修改 \(b[x]\)与 \(b[y+1]\)。
\(b[x]=b[x]+k\)，\(b[y+1]=b[y+1]-k\)。
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
#define N 2000010
using namespace std;
int n,m,tree[N],a[N];
int lowbit(int x){
return x & (-x);
}
void add(int x,int k){
while(x<=n){
tree[x]+=k;
x+=lowbit(x);
}
}
int ask(int x){
int ans=0;
while(x>=1){
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
int flag,x,y,k;
for(int i=1;i<=m;i++){
scanf("%d",&flag);
if(flag==1){
scanf("%d %d %d",&x,&y,&k);
add(x,k);
add(y+1,-k);
}
else{
scanf("%d",&x);
printf("%d\n",ask(x)+a[x]);
}
}
return 0;
}和归并排序求逆序对类似，树状数组同样是在 \(O(n\ log\ n)\) 的时间里求逆序对的。
逆序对就是序列中 \(a[i]>a[j]\) 且 \(i<j\) 的情况下的有序对。
我们可以先按照权值从大到小排序,现在要求的就是对于一个点有多少在他前面的点下标小于这个点。
然后用树状数组维护。从头到尾扫一遍，对于每个点，答案就是在这个点下标之前的下标有几个已经被访问过。
在将这个点在树状数组中+1，表示为被访问过。
但是要注意判重复的元素，同时排序时以序号大小作为第二关键字。（想一想为什么）
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#define N 500010
using namespace std;
int n,tree[N<<2];
long long ans=0;
struct node{
int x,id;
}a[N];
int read(){
int x=0,f=1;
char c=getchar();
while(c<'0' || c>'9') f=(f=='-')?-1:1,c=getchar();
while(c>='0' && c<='9') x=x*10+c-48,c=getchar();
return f*x;
}
int lowbit(int x){
return x & -x;
}
bool cmp(node a,node b){
if(a.x==b.x) return a.id>b.id;
return a.x>b.x;
}
void add(int x,int k){
while(x<=n){
tree[x]+=k;
x+=lowbit(x);
}
return;
}
int ask(int x){
int ans=0;
while(x>0){
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
int main(){
n=read();
for(int i=1;i<=n;i++)
a[i].id=i,a[i].x=read();
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
ans+=ask(a[i].id),add(a[i].id,1);
printf("%lld\n",ans);
return 0;
}A Simple Problem with Integers
其实这个一般用线段树实现，但是也不是没有可能用树状数组实现的啦。(〃‘▽‘〃)
我们已经讨论过区间修改，单点查询问题和，我们知道可以用差分解决。
假设查分数组为 \(b[]\)，那么 \(a\) 的前缀和 \(a[1\)~\(x]\) 的整体增加值就是：
\[\sum _{i=1}^x \sum_{j=1}^i b[j]\]
经过一系列的 玄学 数学推导，上式等于：
\[(x+1 \sum_{i=1}^x b[i]-\sum _{i=1}^x i\times b[i])\]
所以增加一个树状数组来记录 \(i\times b[i]\) 的前缀和即可（假设用 \(tree[i][1]\) 表示）。
那么，核心的加点操作就是：
add(0,x,k);
add(0,y+1,-k);
add(1,x,x*k);
add(1,y+1,-(y+1)*k);答案就是：
sum[y]+(y+1)*ask(0,y)-ask(1,y)-(sum[x-1]+x*ask(0,x-1)-ask(1,x-1))
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define N 100010
using namespace std;
int n,m,a[N];
long long tree[2][N],sum[N];
int read(){
int x=0,f=1;
char c=getchar();
while(c<'0' || c>'9') f=(c=='-')?-1:1,c=getchar();
while(c>='0' && c<='9') x=x*10+c-48,c=getchar();
return f*x;
}
int lowbit(int x){
return x & -x;
}
long long ask(int type,int x){
long long ans=0;
while(x>0){
ans+=tree[type][x];
x-=lowbit(x);
}
return ans;
}
void add(int type,int x,int k){
while(x<=n){
tree[type][x]+=k;
x+=lowbit(x);
}
return;
}
int main(){
n=read();m=read();
for(int i=1;i<=n;i++){
a[i]=read();
sum[i]=sum[i-1]+a[i];
}
char c[2];
int x,y,k;
for(int i=1;i<=m;i++){
scanf("%s",c);
if(c[0]=='C'){
x=read();y=read();k=read();
add(0,x,k);
add(0,y+1,-k);
add(1,x,x*k);
add(1,y+1,-(y+1)*k);
}
else{
x=read();y=read();
long long ans=sum[y]+(y+1)*ask(0,y)-ask(1,y);
ans-=sum[x-1]+x*ask(0,x-1)-ask(1,x-1);
printf("%lld\n",ans);
}
}
return 0;
}其实也没有那么难的啦。
显然一个 ?? 的编号 = 它前面比它高的 ?? 数（即 \(a[i]\)）+ 它后面比它高的 ?? 数 + 1
我们建立一个长度为 \(n\) 的 \(01\) 串 \(b\)，那么起初全部为 \(0\)。然后 \(n\)~\(1\) 倒序处理每一个 \(a[i]\)：
也就是说我们要实时维护一个 01 序列，支持查询并修改第 \(k\) 个 0 的位置。
显然用 树状数组 + 二分即可。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define N 100010
using namespace std;
int n,ans[N],a[N],tree[N];
int read(){
int x=0,f=1;
char c=getchar();
while(c<'0' || c>'9') f=(c=='-')?-1:1,c=getchar();
while(c>='0' && c<='9') x=x*10+c-48,c=getchar();
return x*f;
}
int lowbit(int x){
return x&-x;
}
int ask(int x){
int ans=0;
while(x>0){
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
void add(int x,int k){
while(x<=n){
tree[x]+=k;
x+=lowbit(x);
}
return;
}
int main(){
n=read();
a[1]=0;
for(int i=2;i<=n;i++) a[i]=read();
for(int i=n;i>=1;i--){
int l=1,r=n,mid;
while(l<r){
mid=(l+r)>>1;
if(mid-ask(mid)>a[i]) r=mid;
else l=mid+1;
}
ans[i]=l;
add(l,1);
}
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}树状数组的用途还有许多，以后会继续 \(Update\)。（咕咕咕）
特别鸣谢：LZshuing 的优秀文章。
完结撒花。
原文：https://www.cnblogs.com/lpf-666/p/12543665.html