登录
← 返回首页 | 代码片段 › 2 数据结构 › 2.5 树状数组 › 树状数组 / 搜索
JSON MD

2.5 树状数组

树状数组 bit
24 行
CPP JSON
【树状数组(Fenwick Tree / BIT)模板类】 ▪ BIT(n, in) — 构造函数,大小为 n,用 in[] 数组预处理填值(每个位置做一次 add) ▪ add(x, v) — 单点更新:位置 x 增加 v,通过 x+=lowbit(x) 向上更新所有父节点 ▪ ask(x) — 前缀和查询:查询 [1, x] 的和,通过 x-=lowbit(x) 向上累加 ▪ ask(l, r) — 区间和查询:差分实现 ask(r) - ask(l-1) 所有操作 O(log N),常数远小于线段树。适用于动态维护前缀和、求逆序对等。
C++ 24 行 CPP
template<class T> struct BIT {
    int n;
    vector<T> w;
    BIT(int n, auto &in) : n(n), w(n + 1) { // 预处理填值
        for (int i = 1; i <= n; i++) {
            add(i, in[i]);
        }
    }
    void add(int x, T v) {
        for (; x <= n; x += x & -x) {
            w[x] += v;
        }
    }
    T ask(int x) { // 前缀和查询
        T ans = 0;
        for (; x; x -= x & -x) {
            ans += w[x];
        }
        return ans;
    }
    T ask(int l, int r) { // 差分实现区间和查询
        return ask(r) - ask(l - 1);
    }
};
一维:区间修改,区间查询 add
33 行
CPP JSON
【一维:区间修改,区间查询】 树状数组(Fenwick Tree / BIT)模板,支持单点修改与区间查询。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re v) — 加法更新 void add(Re L,Re R,Re v) — 加法更新 LL ask(Re x) — 核心算法函数 LL ask(Re L,Re R) — 核心算法函数 核心结构体:BIT 关键配置: N=1e6+3 复杂度:单次操作 O(log N),空间 O(N) 适用场景:动态前缀和、逆序对统计、二维偏序问题
C++ 32 行 CPP
/*
            n        n
S[x]= (x+1)*��A[i] - ��i*A[i]
           i=1      i=1
*/
#include<cstdio>
#define LL long long
#define Re register int
const int N=1e6+3;
int n,x,y,z,T,op;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct BIT{
    LL C1[N],C2[N];
    inline void add(Re x,Re v){Re i=x;while(i<=n)C1[i]+=v,C2[i]+=(LL)x*v,i+=i&-i;}
    inline void add(Re L,Re R,Re v){add(L,v),add(R+1,-v);}
    inline LL ask(Re x){Re i=x;LL ans=0;while(i)ans+=(x+1)*C1[i]-C2[i],i-=i&-i;return ans;}
    inline LL ask(Re L,Re R){return ask(R)-ask(L-1);}
}TR;
int main(){
    in(n),in(T);
    for(Re i=1;i<=n;++i)in(x),TR.add(i,i,x);
    while(T--){
        in(op),in(x),in(y);
        if(op<2)in(z),TR.add(x,y,z);
        else printf("%lld\n",TR.ask(x,y));
    }
}
一维:区间修改,单点查询 add
27 行
CPP JSON
【一维:区间修改,单点查询】 树状数组(Fenwick Tree / BIT)模板,支持单点修改与区间查询。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re v) — 加法更新 void add(Re L,Re R,Re v) — 加法更新 LL ask(Re x) — 核心算法函数 核心结构体:BIT 关键配置: N=5e5+3 复杂度:单次操作 O(log N),空间 O(N) 适用场景:动态前缀和、逆序对统计、二维偏序问题
C++ 26 行 CPP
#include<cstdio>
#define LL long long
#define Re register int
const int N=5e5+3;
int n,x,y,z,T,op;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct BIT{
    LL C[N];
    inline void add(Re x,Re v){while(x<=n)C[x]+=v,x+=x&-x;}
    inline void add(Re L,Re R,Re v){add(L,v),add(R+1,-v);}
    inline LL ask(Re x){LL ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}
}TR;
int main(){
    in(n),in(T);
    for(Re i=1;i<=n;++i)in(x),TR.add(i,i,x);
    while(T--){
        in(op),in(x);
        if(op<2)in(y),in(z),TR.add(x,y,z);
        else printf("%lld\n",TR.ask(x));
    }
}
一维:单点修改,区间查询 add
27 行
CPP JSON
【一维:单点修改,区间查询】 树状数组(Fenwick Tree / BIT)模板,支持单点修改与区间查询。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re v) — 加法更新 LL ask(Re x) — 核心算法函数 LL ask(Re L,Re R) — 核心算法函数 核心结构体:BIT 关键配置: N=5e5+3 复杂度:单次操作 O(log N),空间 O(N) 适用场景:动态前缀和、逆序对统计、二维偏序问题
C++ 26 行 CPP
#include<cstdio>
#define LL long long
#define Re register int
const int N=5e5+3;
int n,x,y,T,op;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct BIT{
    LL C[N];
    inline void add(Re x,Re v){while(x<=n)C[x]+=v,x+=x&-x;}
    inline LL ask(Re x){LL ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}
    inline LL ask(Re L,Re R){return ask(R)-ask(L-1);}
}TR;
int main(){
    in(n),in(T);
    for(Re i=1;i<=n;++i)in(x),TR.add(i,x);
    while(T--){
        in(op),in(x),in(y);
        if(op<2)TR.add(x,y);
        else printf("%ld\n",TR.ask(x,y));
    }
}
二维:区间修改,区间查询 add
52 行
CPP JSON
【二维:区间修改,区间查询】 二维树状数组(2D BIT),支持矩阵子区域的前缀和/差分维护。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re v) — 加法更新 void add(Re x1,Re y1,Re x2,Re y2,Re z) — 加法更新 LL ask(Re x,Re y) — 核心算法函数 LL ask(Re x1,Re y1,Re x2,Re y2) — 核心算法函数 核心结构体:BIT 关键配置: N=2048+3 复杂度:单次操作 O(log N),空间 O(N) 适用场景:动态前缀和、逆序对统计、二维偏序问题
C++ 51 行 CPP
/*
                    n   m                 n   m                   n   m             n   m
s[x][y]=(x+1)*(y+1)*��  ��a[i][j] - (y+1)*��  ��a[i][j]*i - (x+1)*��  ��a[i][j]*j + ��  ��a[i][j]*i*j
                   i=1 j=1               i=1 j=1                 i=1 j=1           i=1 j=1
*/
#include<cstdio>
#define y1 yyyy
#define LL long long
#define Re register int
const int N=2048+3;
int n,m,x,x1,y1,x2,y2,op;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct BIT{
    LL C1[N][N],C2[N][N],C3[N][N],C4[N][N];
    inline void add(Re x,Re y,Re v){
        Re i=x;
        while(i<=n){
            Re j=y;
            while(j<=m)C1[i][j]+=v,C2[i][j]+=(LL)x*v,C3[i][j]+=(LL)y*v,C4[i][j]+=(LL)x*y*v,j+=j&-j;
            i+=i&-i;
        }
    }
    inline void add(Re x1,Re y1,Re x2,Re y2,Re z){
        add(x1,y1,z),add(x1,y2+1,-z),add(x2+1,y1,-z),add(x2+1,y2+1,z);
    }
    inline LL ask(Re x,Re y){
        Re i=x;LL ans=0;
        while(i){
            Re j=y;
            while(j)ans+=(LL)(x+1)*(y+1)*C1[i][j]-(LL)(y+1)*C2[i][j]-(LL)(x+1)*C3[i][j]+C4[i][j],j-=j&-j;
            i-=i&-i;
        }
        return ans;
    }
    inline LL ask(Re x1,Re y1,Re x2,Re y2){
        return ask(x2,y2)-ask(x2,y1-1)-ask(x1-1,y2)+ask(x1-1,y1-1);
    }
}TR;
int main(){
    in(n),in(m);
    while(~scanf("%d",&op)){
        in(x1),in(y1),in(x2),in(y2);
        if(op<2)in(x),TR.add(x1,y1,x2,y2,x);
        else printf("%lld\n",TR.ask(x1,y1,x2,y2));
    }
}
二维:区间修改,单点查询 add
56 行
CPP JSON
【二维:区间修改,单点查询】 二维树状数组(2D BIT),支持矩阵子区域的前缀和/差分维护。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re v) — 加法更新 void add(Re x1,Re y1,Re x2,Re y2,Re z) — 加法更新 LL ask(Re x,Re y) — 核心算法函数 核心结构体:BIT 关键配置: N=4096+3 复杂度:单次操作 O(log N),空间 O(N) 适用场景:动态前缀和、逆序对统计、二维偏序问题
C++ 55 行 CPP
/*
(样例输入)
输入:
2 3 8
1 1 2 2 3 2
1 1 1 2 2 -3
2 1 1 
2 1 2 
2 1 3
2 2 1
2 2 2
2 2 3

输出
-3
-1
2
-3
-1
2
*/
#include<cstdio>
#define y1 yyyy
#define LL long long
#define Re register int
const int N=4096+3;
int n,m,T,x,x1,y1,x2,y2,op;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct BIT{
    LL C[N][N];
    inline void add(Re x,Re y,Re v){
        while(x<=n){Re j=y;while(j<=m)C[x][j]+=v,j+=j&-j;x+=x&-x;}
    }
    inline void add(Re x1,Re y1,Re x2,Re y2,Re z){
        add(x1,y1,z),add(x1,y2+1,-z),add(x2+1,y1,-z),add(x2+1,y2+1,z);
    }
    inline LL ask(Re x,Re y){
        LL ans=0;
        while(x){Re j=y;while(j)ans+=C[x][j],j-=j&-j;x-=x&-x;}
        return ans;
    }
}TR;
int main(){
    in(n),in(m),in(T);
    while(T--){
        in(op),in(x1),in(y1);
        if(op<2)in(x2),in(y2),in(x),TR.add(x1,y1,x2,y2,x);
        else printf("%lld\n",TR.ask(x1,y1));
    }
}
二维:单点修改,区间查询 add
33 行
CPP JSON
【二维:单点修改,区间查询】 二维树状数组(2D BIT),支持矩阵子区域的前缀和/差分维护。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re v) — 加法更新 LL ask(Re x,Re y) — 核心算法函数 LL ask(Re x1,Re y1,Re x2,Re y2) — 核心算法函数 核心结构体:BIT 关键配置: N=4096+3 复杂度:单次操作 O(log N),空间 O(N) 适用场景:动态前缀和、逆序对统计、二维偏序问题
C++ 32 行 CPP
#include<cstdio>
#define y1 yyyy
#define LL long long
#define Re register int
const int N=4096+3;
int n,m,x1,y1,x2,y2,op;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct BIT{
    LL C[N][N];
    inline void add(Re x,Re y,Re v){
        while(x<=n){Re j=y;while(j<=m)C[x][j]+=v,j+=j&-j;x+=x&-x;}
    }
    inline LL ask(Re x,Re y){
        LL ans=0;
        while(x){Re j=y;while(j)ans+=C[x][j],j-=j&-j;x-=x&-x;}
        return ans;
    }
    inline LL ask(Re x1,Re y1,Re x2,Re y2){return ask(x2,y2)-ask(x2,y1-1)-ask(x1-1,y2)+ask(x1-1,y1-1);}
}TR;
int main(){
    in(n),in(m);
    while(~scanf("%d",&op)){
        in(x1),in(y1),in(x2);
        if(op<2)TR.add(x1,y1,x2);
        else in(y2),printf("%lld\n",TR.ask(x1,y1,x2,y2));
    }
}
单点修改 ,区间查询 (Max) 取Max
30 行
CPP JSON
【单点修改 ,区间查询 (Max)(取Max)】 树状数组(Fenwick Tree / BIT)模板,支持单点修改与区间查询。 核心函数: void in(Re &x) — 核心算法函数 int max(Re a,Re b) — 核心算法函数 void add(Re x,Re v) — 加法更新 int ask(Re l,Re r) — 核心算法函数 核心结构体:BIT 关键配置: N=1e5+3 复杂度:单次操作 O(log N),空间 O(N) 适用场景:动态前缀和、逆序对统计、二维偏序问题
C++ 29 行 CPP
#include<cstdio>
#define LL long long
#define Re register int
const int N=1e5+3;
int n,x,y,T,A[N];
inline void in(Re &x){
    int f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=f?-x:x;
}
inline int max(Re a,Re b){return a>b?a:b;}
struct BIT{
    int C[N];
    inline void add(Re x,Re v){while(x<=n)C[x]=max(C[x],v),x+=x&-x;}
    inline int ask(Re l,Re r){
        Re ans=0;
        while(l<=r){
            while(r-(r&-r)>=l)ans=max(ans,C[r]),r-=r&-r;
            ans=max(ans,A[r--]);
        }
        return ans;
    }
}TR;
int main(){
    in(n),in(T);
    for(Re i=1;i<=n;++i)in(A[i]),TR.add(i,A[i]);
    while(T--)in(x),in(y),printf("%d\n",TR.ask(x,y));
}
普通平衡树 树状数组
49 行
CPP JSON
【普通平衡树(树状数组)】 树状数组(Fenwick Tree / BIT)模板,支持单点修改与区间查询。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re v) — 加法更新 int ask(Re x) — 核心算法函数 int ask_kth(Re k) — 核心算法函数 F(i,1,T) — 核心算法函数 F(i,1,T) — 核心算法函数 关键配置: N=1e5+3,inf=2147483647 复杂度:单次操作 O(log N),空间 O(N) 适用场景:动态前缀和、逆序对统计、二维偏序问题
C++ 48 行 CPP
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstdio>
#define Re register int
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
#define P(x) if(op[i]==x)
using namespace std;
const int N=1e5+3,inf=2147483647;
int m,T,fu,C[N],a[N],b[N],Q[N],op[N]; 
inline void in(Re &x){
    x=fu=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline void add(Re x,Re v){while(x<=m)C[x]+=v,x+=x&-x;}
inline int ask(Re x){
	Re ans=0;
	while(x>0)ans+=C[x],x-=x&-x;
	return ans;
}
inline int ask_kth(Re k){
	Re l=0,r=m;
	while(l<r){
		Re mid=l+r>>1;
		if(ask(mid)>=k)r=mid;
		else l=mid+1;
	}
	return b[l];
}
int main(){
	in(T); 
    F(i,1,T){
    	in(op[i]),in(Q[i]);
    	if(op[i]!=4)b[++m]=Q[i];
    }
    sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
    F(i,1,T){
    	P(1)add(lo(Q[i]),1);
    	P(2)add(lo(Q[i]),-1);
		P(3)printf("%d\n",ask(lo(Q[i])-1)+1);
		P(4)printf("%d\n",ask_kth(Q[i]));
		P(5)printf("%d\n",ask_kth(ask(lo(Q[i])-1)));
		P(6)printf("%d\n",ask_kth(ask(lo(Q[i]))+1));
    }
}
炸勃龙 树状数组+扩展欧拉定理
47 行
CPP JSON
【炸勃龙(树状数组+扩展欧拉定理)】 树状数组(Fenwick Tree / BIT)模板,支持单点修改与区间查询。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re k) — 加法更新 LL ask(Re x) — 核心算法函数 LL mi(Re x,Re k,Re P) — 核心算法函数 LL sakura(Re l,Re r,Re P) — 后缀数组 关键配置: N=5e5+3,Np=2e7 复杂度:单次操作 O(log N),空间 O(N) 适用场景:动态前缀和、逆序对统计、二维偏序问题
C++ 46 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#define LL long long
#define Re register LL
#define F(a,b) for(i=a;i<=b;++i)
const int N=5e5+3,Np=2e7;
LL i,j,n,x,l,r,K,T,fu,cnt,c[N],C[N],pan[Np+1],pri[Np+1],phi[Np+1];char ch;
inline void in(Re &x){
    x=fu=0;ch=getchar();
    while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x=fu?-x:x;
}
inline void add(Re x,Re k){while(x<=n)C[x]+=k,x+=x&-x;}
inline LL ask(Re x){Re tmp=0;while(x)tmp+=C[x],x-=x&-x;return tmp;}
inline LL mi(Re x,Re k,Re P){
    Re s=1,ok=0,flag=0;ok|=(x>=P);x%=P;
    while(k){
        if(k&1){s*=x;flag|=(ok||s>=P);s%=P;}
        x*=x;ok|=(x>=P);x%=P;k>>=1;
    }
    return s+(flag?P:0);
}

inline LL sakura(Re l,Re r,Re P){
    if(P==1|l>r)return 1;
    return mi(ask(l),sakura(l+1,r,phi[P]),P);
}
int main(){
    for(i=2;i<=Np;++i){
        if(!pan[i])pri[++cnt]=i,phi[i]=i-1;
        for(j=1;j<=cnt;++j){
      		if(i*pri[j]>Np)break;
      		pan[i*pri[j]]=1;
      		if(i%pri[j])phi[i*pri[j]]=phi[i]*(pri[j]-1);
      		else{phi[i*pri[j]]=phi[i]*pri[j];break;}
   		}
    }
    in(n),in(T);
    F(1,n)in(x),add(i,x-l),l=x;
    while(T--){
        in(K),in(l),in(r),in(x);
        if(K<2)add(l,x),add(r+1,-x);
        else printf("%lld\n",sakura(l,r,x)%x);
    }
}
已复制