树状数组学习笔记

Hello, 欢迎登录 or 注册!

/ 1评 / 0赞

本文作者：  本文分类：编程学习笔记  浏览：1841
阅读时间：5168字, 约5.5-8.5分钟

Part 1 基础

树状数组可以解决大部分基于区间上的更新以及求和问题。

树状数组修改和查询的复杂度都是 $O(logn)$，而且相比线段树系数要少很多，比传统数组要快，而且容易写。

缺点是遇到复杂的区间问题还是不能解决，功能还是有限。

单点更新、区间查询

核心：

int a[500005],c[500005];
int lowbit(int x) {
    return x & (-x);
}
void updata(int i,int k) { //i的位置加上k
    while(i <= n) {
        c[i] += k;
        i += lowbit(i);
    }
}
int getsum(int i) { //求a[1]到a[i]的和 
    int res = 0;
    while(i > 0) {
        res += c[i];
        i -= lowbit(i);
    }
    return res; 
}

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[500005],c[500005];
int lowbit(int x) {
    return x & (-x);
}
void updata(int i,int k) { //i的位置加上k
    while(i <= n) {
        c[i] += k;
        i += lowbit(i);
    }
}
int getsum(int i) { //求a[1]到a[i]的和 
    int res = 0;
    while(i > 0) {
        res += c[i];
        i -= lowbit(i);
    }
    return res; 
}
int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        scanf("%d",&a[i]);
        updata(i,a[i]);
    }
    while(m--) {
        int opt;
        int x,y;
        scanf("%d%d%d",&opt,&x,&y);
        if (opt == 1) updata(x,y);
        else if (opt == 2) printf("%d\n",getsum(y) - getsum(x - 1));
    }
    return 0;
}

区间更新、单点查询

这就是第一个问题，如果题目是让你把 $x-y$ 区间内的所有值全部加上k或者减去 $k$ ，然后查询操作是问某个点的值，这种时候该怎么做呢。如果是像上面的树状数组来说，就必须把 $x-y$ 区间内每个值都更新，这样的复杂度肯定是不行的，这个时候，就不能再用数据的值建树了，这里我们引入差分，利用差分建树。

核心：

int n,m;
int a[50005] = {0},c[50005]; //对应原数组和树状数组

int lowbit(int x) {
    return x & (-x);
}

void updata(int i,int k) {   //在i位置加上k
    while(i <= n) {
        c[i] += k;
        i += lowbit(i);
    }
}

int getsum(int i) {       //求D[1 - i]的和，即A[i]值
    int res = 0;
    while(i > 0) {
        res += c[i];
        i -= lowbit(i);
    }
    return res;
}

int main() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
        updata(i,a[i] - a[i-1]);   //输入初值的时候，也相当于更新了值
    }

    //[x,y]区间内加上k
    updata(x,k);    //A[x] - A[x-1]增加k
    updata(y+1,-k);        //A[y+1] - A[y]减少k

    //查询i位置的值
    int sum = getsum(i);

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[500005],c[500005];
int opt,x,y,k;
int lowbit(int x) {
    return x & (-x);
}
void updata(int i,int k) { //i的位置加上k
    while(i <= n) {
        c[i] += k;
        i += lowbit(i);
    }
}
int getsum(int i) { //求a[1]到a[i]的和
    int res = 0;
    while(i > 0) {
        res += c[i];
        i -= lowbit(i);
    }
    return res;
}
int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        scanf("%d",&a[i]);
        updata(i,a[i] - a[i-1]); 
    }
    while(m--) {
        scanf("%d",&opt);
        if (opt == 1) {
            scanf("%d%d%d",&x,&y,&k);
            updata(x,k);
            updata(y + 1,-k);
        }
        else if (opt == 2) {
            scanf("%d",&x);
            printf("%d\n",getsum(x));
        }
    }
    return 0;
}

区间更新、区间查询

还是差分。

int n,m;
int a[50005] = {0};
int sum1[50005];    //(D[1] + D[2] + ... + D[n])
int sum2[50005];    //(1*D[1] + 2*D[2] + ... + n*D[n])

int lowbit(int x) {
    return x & (-x);
}

void updata(int i,int k) {
    int x = i;    //因为x不变，所以得先保存i值
    while(i <= n) {
        sum1[i] += k;
        sum2[i] += k * (x-1);
        i += lowbit(i);
    }
}

int getsum(int i) {       //求前缀和
    int res = 0, x = i;
    while(i > 0) {
        res += x * sum1[i] - sum2[i];
        i -= lowbit(i);
    }
    return res;
}

int main() {
    cin>>n;
    for(int i = 1; i <= n; i++) {
        cin>>a[i];
        updata(i,a[i] - a[i-1]);   //输入初值的时候，也相当于更新了值
    }

    //[x,y]区间内加上k
    updata(x,k);    //A[x] - A[x-1]增加k
    updata(y+1,-k);        //A[y+1] - A[y]减少k

    //求[x,y]区间和
    int sum = getsum(y) - getsum(x-1);

    return 0;
}

区间更新、区间查询。

注意 $\texttt{long long}$。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a1[200005],a2[200005],mian = 0;
ll n,m;
ll lowbit(ll x) {
    return x & (-x);
}
void updata(ll x,ll v) { 
    for(ll p=x; x<=n; a1[x] += v,a2[x] += (ll)v * p,x += lowbit(x)); 
}
ll getsum(ll x) { 
    ll res = 0;
    for(ll p=x; x; res += (p + 1) * a1[x] - a2[x],x -= lowbit(x));
    return res;
}
int main() {
    cin>>n>>m;
    for(ll i=1,x; i<=n; i++) {
        scanf("%lld",&x);
        updata(i,x);
        updata(i + 1,-x);
    }
    for(ll i=1,opt; i<=m; i++) {
        scanf("%lld",&opt);
        if(opt == 1) {
            ll l,r,x;
            scanf("%lld%lld%lld",&l,&r,&x);
            updata(l,x);
            updata(r + 1,-x);
        }
        if(opt == 2) {
            ll x;
            scanf("%lld",&x);
            mian += x;
        }
        if(opt == 3) {
            ll x;
            scanf("%lld",&x);
            mian -= x;
        }
        if(opt == 4) {
            ll l,r;
            scanf("%lld%lld",&l,&r);
            printf("%lld\n",getsum(r) - getsum(l - 1) + (l == 1) * mian);
        }
        if(opt == 5) printf("%lld\n",getsum(1) + mian);
    }
    return 0;
}

区间修改，单点查询。

差分建树。

#include <bits/stdc++.h>
using namespace std;
int n,m;
int opt,a,b;
int c[10000005] = {0};
int lowbit(int x) {
    return x & (-x);
}
void updata(int i,int k) {   //在i位置加上k
    while(i <= n) {
        c[i] += k;
        i += lowbit(i);
    }
}

int getsum(int i) {       //求D[1 - i]的和，即A[i]值
    int res = 0;
    while(i > 0) {
        res += c[i];
        i -= lowbit(i);
    }
    return res;
}
int main() {
    cin>>n>>m;
    while(m--) {
        scanf("%d",&opt);
        if (opt == 0) {
            scanf("%d%d",&a,&b);
            updata(a,1);
            updata(b + 1,-1);
        }
        else {
            scanf("%d",&a);
            printf("%d\n",getsum(a));
        }
    }
    return 0;
}

Part 2 进阶

二维树状数组

在一维树状数组中，
```tree[x]```（树状数组中的那个“数组”）记录的是右端点为 $x$，长度为 $lowbit(x)$ 的区间的区间和。
那么在二维树状数组中，可以类似地定义 ```tree[x][y]``` 记录的是右下角为 $(x, y)$，高为 $lowbit(x)$, 宽为 $lowbit(y)$ 的区间的区间和。

单点修改、区间查询

void add(int x, int y, int z) { //将点(x, y)加上z
    int memo_y = y;
    while(x <= n) {
        y = memo_y;
        while(y <= n)
            tree[x][y] += z, y += y & -y;
        x += x & -x;
    }
}
void ask(int x, int y) { //求左上角为(1,1)右下角为(x,y) 的矩阵和
    int res = 0, memo_y = y;
    while(x) {
        y = memo_y;
        while(y)
            res += tree[x][y], y -= y & -y;
        x -= x & -x;
    }
}

Code：

#include <bits/stdc++.h>
#define re return
#define ll long long
#define lowbit(x) (x&(-x))
#define inc(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
template<typename T>inline void rd(T&x) {
    char c;
    bool f=0;
    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
    x=c^48;
    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);
    if(f)x=-x;
}
const int maxn=5000;
ll n,m;
ll c[maxn][maxn];
inline void add(ll x,ll y,ll z) { //将点(x, y)加上z
    for(ll i=x; i<=n; i+=lowbit(i))
        for(ll j=y; j<=m; j+=lowbit(j))
            c[i][j]+=z;
}
inline ll sum(ll x,ll y) { //求左上角为(1,1)右下角为(x,y) 的矩阵和
    ll res=0;
    for(ll i=x; i; i-=lowbit(i))
        for(ll j=y; j; j-=lowbit(j))
            res+=c[i][j];

    re res;
}

int main() {
    ll a,b,x,y,z,opt;
    rd(n); rd(m);
    while(~(scanf("%lld",&opt))) {
        if(opt==1) {
            rd(x),rd(y),rd(z);
            add(x,y,z);
        } else {
            rd(a),rd(b),rd(x),rd(y);
            printf("%lld\n",sum(x,y) + sum(a - 1,b - 1) - sum(x,b - 1) - sum(a - 1,y));
        }
    }
    return 0;
}

区间修改、单点查询

void add(int x, int y, int z) {
    int memo_y = y;
    while(x <= n) {
        y = memo_y;
        while(y <= n)
            tree[x][y] += z, y += y & -y;
        x += x & -x;
    }
}
void range_add(int xa, int ya, int xb, int yb, int z) {
    add(xa, ya, z);
    add(xa, yb + 1, -z);
    add(xb + 1, ya, -z);
    add(xb + 1, yb + 1, z);
}
void ask(int x, int y) {
    int res = 0, memo_y = y;
    while(x) {
        y = memo_y;
        while(y)
            res += tree[x][y], y -= y & -y;
        x -= x & -x;
    }
}

关于作者

  1. EricNTH说道：
    2021年2月4日 下午4:51

    2021-2-4 16:51 审核通过
    682！

    回复

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注