树状数组笔记

代码源数据结构中级课

第一课：树状数组笔记

• • • 树状数组1
    • 树状数组2
    • 逆序对2
    • 树状数组二分
    • 二维树状数组

思路： l o w b i t lowbit lowbit：求二进制数最低位 1 1 1和尾端 0 0 0构成的二进制数， l o w b i t ( x ) = x & ( − x ) lowbit(x)=x&(-x) lowbit(x)=x&(−x)
树状数组 c i = ∑ j = i − l o w b i t ( i ) + 1 i a j c_i=sum_{j=i-lowbit(i)+1}^ia_{j} ci​=∑j=i−lowbit(i)+1i​aj​
单点加：

void modify(int x,ll val){
    for(;x<=n;x+=x&(-x)) c[i]+=val;
}

前缀和查询：

ll query(int x){
    ll s=0;
    for(;x;x-=x&(-x)) s+=c[i];
    return s;
}

在此基础上修改 a x = d a_x=d ax​=d，只需要： m o d i f y ( x , d − a [ x ] ) , a [ x ] = d modify(x,d-a[x]),a[x]=d modify(x,d−a[x]),a[x]=d即可

C o d e : Code: Code:

#include 
using namespace std;
#define endl 'n';
typedef long long ll;
typedef pair PII;
const int N=2e5+10,mod=998244353;
template
void read(T &x){
	x=0; char c; int sign=1;
	do{ c=getchar(); if(c=='-') sign=-1;}while(!isdigit(c));
	do{ x=x*10+c-'0',c=getchar();}while(isdigit(c));
	x*=sign;
}
int a[N],n,q,x;
ll c[N];
void modify(int x,ll val){
	for(;x<=n;x+=x&(-x)) c[x]+=val;
}
ll query(int x){
	ll s=0;
	for(;x;x-=x&(-x)) s+=c[x];
	return s;
}
int main(){
	read(n),read(q);
	for(int i=1;i<=n;i++) {
		read(a[i]);
		modify(i,a[i]);
	}
	while(q--){
		int op;read(op);
		if(op==1){
			int x,d;
			read(x),read(d);
			modify(x,d-a[x]);
			a[x]=d;
		}else{
			int x;read(x);
			printf("%lldn",query(x));
		}
	}
	return 0;
}

思路：考虑差分，对 [ l , r ] [l,r] [l,r]的区间都加上 d d d，只需要在差分数组 d [ l ] d[l] d[l]处 + d +d +d， d [ r + 1 ] d[r+1] d[r+1]处 − d -d −d
原数组和差分数组对应关系为： a i = ∑ k = 1 i d k a_i=sum_{k=1}^{i} d_k ai​=∑k=1i​dk​
那么 ∑ i = 1 x a i = ∑ i = 1 x ( x + 1 − i ) ∗ d i = ( x + 1 ) ∑ i = 1 x d i − ∑ i = 1 x i ∗ d i sum_{i=1}^x a_i=sum_{i=1}^x (x+1-i)*d_i=(x+1)sum_{i=1}^xd_i-sum_{i=1}^x i*d_i ∑i=1x​ai​=∑i=1x​(x+1−i)∗di​=(x+1)∑i=1x​di​−∑i=1x​i∗di​
对于 ∑ i = 1 x d i sum_{i=1}^xd_i ∑i=1x​di​， ∑ i = 1 x i ∗ d i sum_{i=1}^x i*d_i ∑i=1x​i∗di​，维护两个树状数组即可

C o d e : Code: Code:

#include 
using namespace std;
#define endl 'n';
typedef long long ll;
typedef unsigned long long u64;
typedef pair PII;
const int N=2e5+10,mod=998244353;
template
void read(T &x){
	x=0; char c; int sign=1;
	do{ c=getchar(); if(c=='-') sign=-1;}while(!isdigit(c));
	do{ x=x*10+c-'0',c=getchar();}while(isdigit(c));
	x*=sign;
}
int a[N],n,q,x;
template
struct BIT{
	T c[N];
	void modify(int x,T val){
		for(;x<=n;x+=x&(-x)) c[x]+=val;
	}
	T query(int x){
		T s=0;
		for(;x;x-=x&(-x)) s+=c[x];
		return s;
	}
};
BIT c1,c2;
int main(){
	read(n),read(q);
	while(q--){
		int op;read(op);
		if(op==1){
			int l,r;read(l),read(r);
			u64 d;read(d);
			c1.modify(l,d);
			c1.modify(r+1,-d);
			c2.modify(l,l*d);
			c2.modify(r+1,(r+1)*(-d));
		}else{
			int x;read(x);
			printf("%llun",(x+1)*c1.query(x)-c2.query(x));
		}
	}
	return 0;
}

思路：把静态问题转化为动态问题+权值开树状数组
对于 j j j从 [ 1 , n ] [1,n] [1,n]循环的时候，统计 a [ 1 , j − 1 ] a_{[1,j-1]} a[1,j−1]​中大于 a j a_j aj​的个数，对于 a [ 1 , j − 1 ] a_{[1,j-1]} a[1,j−1]​维护一个数据结构 D D D，统计完个数之后再将 a j a_j aj​加入 D D D中
那么 D D D满足的操作为： 1. D [ a x ] + = 1 1.D[a_x]+=1 1.D[ax​]+=1， 2. 2. 2.后缀和查询
理解为把 a x a_x ax​当作下标加入 D D D中，那么对于 a [ 1 , x − 1 ] a_{[1,x-1]} a[1,x−1]​中在 D D D中在 a x a_x ax​后面的和即为 a [ 1 , x − 1 ] a_{[1,x-1]} a[1,x−1]​中比 a x a_x ax​大的数的个数，对于这个后缀和查询，只要预处理 a i = n + 1 − a i a_i=n+1-a_i ai​=n+1−ai​即可转化为前缀和查询

C o d e ： Code： Code：

#include 
using namespace std;
#define endl 'n';
typedef long long ll;
typedef unsigned long long u64;
typedef pair PII;
const int N=2e5+10,mod=998244353;
template
void read(T &x){
	x=0; char c; int sign=1;
	do{ c=getchar(); if(c=='-') sign=-1;}while(!isdigit(c));
	do{ x=x*10+c-'0',c=getchar();}while(isdigit(c));
	x*=sign;
}
int n,a[N];
ll c[N];
void modify(int x,ll val){
	for(;x<=n;x+=x&(-x)) c[x]+=val;
}
ll query(int x){
	ll s=0;
	for(;x;x-=x&(-x)) s+=c[x];
	return s;
}
int main(){
	read(n);
	for(int i=1;i<=n;i++) {
		read(a[i]);
		a[i]=n+1-a[i];
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		ans+=query(a[i]);
		modify(a[i],1);
	}
	printf("%lld",ans);
	return 0;
}

思路：直接二分的复杂度为 O ( l o g 2 n ) O(log^2n) O(log2n)，如果在 q u e r y query query时，从最高位开始向最低位循环，如果满足 c [ p o s + ( 1 < < j ) ] < = s c[pos+(1<

C o d e : Code: Code:

#include 
using namespace std;
#define endl 'n';
typedef long long ll;
typedef unsigned long long u64;
typedef pair PII;
const int N=2e5+10,mod=998244353;
template
void read(T &x){
	x=0; char c; int sign=1;
	do{ c=getchar(); if(c=='-') sign=-1;}while(!isdigit(c));
	do{ x=x*10+c-'0',c=getchar();}while(isdigit(c));
	x*=sign;
}
int n,a[N],q;
ll c[N];
void modify(int x,ll val){
	for(;x<=n;x+=x&(-x)) c[x]+=val;
}
ll query(ll s){
	ll pos=0;
	for(int j=18;j>=0;j--){
		if(pos+(1<
			pos+=(1<
	read(n),read(q);
	for(int i=1;i<=n;i++) {
		read(a[i]);
		modify(i,a[i]);
	}
	while(q--){
		int op;read(op);
		if(op==1){
			int x,d;read(x),read(d);
			modify(x,d-a[x]);
			a[x]=d;
		}else{
			ll s;read(s);
			printf("%lldn",query(s));
		}
	}
	return 0;
}

思路： k k k维树状数组的复杂度为 O ( l o g k n ) O(log^kn) O(logkn)

C o d e : Code: Code:

#include 
using namespace std;
#define endl 'n';
typedef long long ll;
typedef unsigned long long u64;
typedef pair PII;
const int N=500+10,mod=998244353;
template
void read(T &x){
	x=0; char c; int sign=1;
	do{ c=getchar(); if(c=='-') sign=-1;}while(!isdigit(c));
	do{ x=x*10+c-'0',c=getchar();}while(isdigit(c));
	x*=sign;
}
int n,m,a[N][N],q;
ll c[N][N];
void modify(int x,int y,ll val){
	for(int i=x;i<=n;i+=i&(-i)) {
		for(int j=y;j<=m;j+=j&(-j)){
			c[i][j]+=val;
		}
	}
}
ll query(int x,int y){
	ll s=0;
	for(int i=x;i;i-=i&(-i)) {
		for(int j=y;j;j-=j&(-j)){
			s+=c[i][j];
		}
	}
	return s;
}
int main(){
	read(n),read(m),read(q);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			read(a[i][j]);
			modify(i,j,a[i][j]);
		}
	}
	while(q--){
		int op;read(op);
		if(op==1){
			int x,y;read(x),read(y);
			ll d;read(d);
			modify(x,y,d-a[x][y]);
			a[x][y]=d;
		}else{
			int x,y;read(x),read(y);
			printf("%lldn",query(x,y));
		}
	}
	return 0;
}