欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

树状数组(单点+区间的所有操作)

程序员文章站 2022-07-13 21:29:24
...

更简洁方便的数据结构--树状数组(基于线段树的实现)

单点更新+区间求和

例:HDU 1161-敌兵布阵

题目大意:给一个初始数组a1、a2、a3...、an
操作1:修改某项的值

操作2:求某段区间[l, r]的和

1、基于线段树的实现
接下来,我们来看如何计算从l到r的和(al, al+1,al+2,al+3....ar)。在基于线段树的实现中,这个和是可以直接求得的。
但是如果我们能够计算出(从1到r的和)-(从1-l的和),同样可以得到l到r的和。也就是说,只要对于任意i,我们都能计算出1到i的部分的和就足够了。
在这样的限制下,会带来哪些改变呢?我们可以发现,线段树上每个节点的右儿子的值都不需要了(因为在计算时如果需要用到这个值,那么它左边兄弟的值一定会用到,这个时候值需要使用它们父亲的值就可以了)。
树状数组(单点+区间的所有操作)

基于上面的思路得到的数据结构就是BIT(树状数组)。比起线段树,BIT实现起来更方便,速度也更快。


2、BIT结构:
BIT使用数组维护下图所示的部分和

树状数组(单点+区间的所有操作)
也就是把线段树中不需要的节点去掉后,再把剩下的节点对应到数组中。让我们对比每个节点对应的区间的长度的节点编号的二进制表示。以1结尾的1,3,5,7的长度是1,最后有1个0的2,6,的长度是2,最后有两个0的4的长度是4......这样,编号的二进制表示就能够和区间非常容易的对应起来。利用这个性质,BIT可以通过非常简单的位运算实现。

3、BIT求和

计算前i项的和需要从i开始,不断把当前位置i的值加到结果中,并从i中减去i的二进制最低位的1,直到i变成0为止。i的二进制的最后一个1可以通过i&-i求得。
树状数组(单点+区间的所有操作)

区间求和的代码实现sum(i) = a[1]+a[2]+a[3]+...+a[i]:
int sum(int i)
{
    int ans = 0;
    while(i > 0) {
        ans += bit[i];
        i -= (i&-i);
    }
    return ans;
}

4、BIT的更新
使第i项的值增加x需要从i开始,不断把当前位置的i的值增加x,并把i加上二进制最低位的1
树状数组(单点+区间的所有操作)
单点更新的代码实现:
void add(LL i, LL add)
{
    while(k <= n) {
        bit[i] += add;
        i += (i & -i);
    }
}

5、BIT的复杂度

总共需要对O(logn)个值进行操作,所以复杂度是O(logn)


例题AC代码:
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#define bug printf("*********\n");
#define mem0(a) memset(a, 0, sizeof(a));
#define mem1(a) memset(a, -1, sizeof(a));
using namespace std;
typedef long long LL;

int bit[100010], n;
string str;

int sum(int i)
{
    int ans = 0;
    while(i > 0) {
        ans += bit[i];
        i -= (i&-i);
    }
    return ans;
}

void add(int i, int x)
{
    while(i <= n) {
        bit[i] += x;
        i += (i&-i);
    }
}

int main()
{
    int T, x, l, r, t = 1;
    scanf("%d", &T);
    while(T --) {
        mem0(bit);
        scanf("%d", &n);
        for(int i = 1; i <= n; i ++) {
            scanf("%d", &x);
            add(i, x);
        }
        printf("Case %d:\n", t ++);
        while(cin>>str && str != "End") {
            scanf("%d%d", &l, &r);
            if(str == "Query") printf("%d\n", sum(r) - sum(l-1));
            else if(str == "Add") add(l, r);
            else add(l, -r);
        }
    }
    return 0;
}

区间更新+单点求值(基于单点更新+区间求和)

例:HDU 1556-Color the ball

操作1:修改某段区间[l, r]的值
操作2:求某项的值


前面我们简单介绍了BIT的作用:可以快速求出某段区间的值,但是我们如何快速修改某段区间的值呢?
这里我们引入另一个数组,叫做差分数组b[],这个数组内装的是什么值呢?
下面给大家解释一下,这里我们的b[i] = a[i]-a[i-1]那么我们的a[i] = b[1]+b[2]+b[3]+....+b[i],所以我们求某个单点的值就又转化成了一个区间求和。
例如:a[] = 1 3 5 9 7 10
那么:b[] = 1 2 2 4 -2 3


那么我们进行区间更新的时候怎么操作呢?
同样对于上面的那个例子,我们要给区间[2,4]内的每一项加1,那么此时我们的b[] = 1 3 2 4 -3 3,与原来的b[]数组相比,由于差分的效果,我们的b[]数组是不是只是把b[2]+1,b[5]-1,除了b[l]和b[r+1],其他地方的差值没有变呐,所以对于区间更新+单点求值的问题,我们又转化成了单点更新+区间求和的问题啦!

求和:所以我们求a[i]就求b[]数组的sum(i)即可
更新:我们更新a[l, r]+x就add(l, x), add(r+1, -x)即可

例题AC代码:

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#define bug printf("*********\n");
#define mem0(a) memset(a, 0, sizeof(a));
#define mem1(a) memset(a, -1, sizeof(a));
using namespace std;
typedef long long LL;

int bit[100010], n;

int sum(int i)
{
    int ans = 0;
    while(i > 0) {
        ans += bit[i];
        i -= (i&-i);
    }
    return ans;
}

void add(int i, int k)
{
    while(i <= n) {
        bit[i] += k;
        i += (i&-i);
    }
}

int main()
{
    int l ,r;
    while(~scanf("%d", &n) && n) {
        mem0(bit); //因为开始所有的差分值都为0
        /*如果有初值的话,就
        a[0] = 0
        for(int i = 1; i <= n; i ++) {
            scanf("%d", &a[i]);
            add(i, a[i] - a[i-1]);
        }
        */
        for(int i = 0; i < n; i ++) {
            scanf("%d%d", &l, &r);
            add(l, 1);
            add(r+1, -1);
        }
        for(int i = 1; i < n; i ++)
            printf("%d ", sum(i));
        printf("%d\n", sum(n));
    }
    return 0;
}

区间更新+区间求和(基于区间更新+单点求和)还是差分的思想,重点

例题:POJ 3468-A Simple Problem with Integers 

操作1:给区间[l, r]的所有数加上x
操作2:求区间[l ,r]内的和


前面我们实现了区间更新+单点求和,那么神仙们一定不会放过区间更新+区间求和的骚操作,确实,大神们也实现了这一操作,接下来我就给大家讲解一下,其实也是非常的简单:

前面的区间更新+单点求值,我们的a[i] = b[1] + b[2] + b[3] +....+ b[i],那么我们推一下区间求和

我们来看看a[1] + a[2] + a[3] + ... + a[n] = b[1] + (b[1]+b[2]) + (b[1]+b[2]+b[3]) + ... + (b[1]+b[2]+b[3]+...+b[n])

                                                               = n*(b[1]+b[2]+b[3]+...+b[n]) - (0*b[1]+1*b[2]+2*b[3]+...+(n-1)*b[n])

那么我们在定义一个数组c[i] = (i-1)*b[i],那么我们的区间[1, n]的a[i]和就为n*sum(b[] ,n) - sum(c[], n)
我们在修改b[i]时同时对c[i]进行维护即可,即add(b[], i, x) 的同时 add(c[], i, (i-1)x)


例如我们要求a[l] ~ a[r]的和,那么我们用b[]数组来代替所有的a[]会是什么样呢?

结果就是:( n*sum(b[], r) - sum(c[], r) ) - ( n*sum(b[], l) - sum(c[], l) )。

例题AC代码:
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#define mem0(a) memset(a, 0, sizeof(a));
#define mem1(a) memset(a, -1, sizeof(a));
using namespace std;
typedef long long LL;


LL n, m, a[100010];
LL bit0[100010], bit1[100010];
char str[2];

LL sum(LL *bit, LL k)
{
    LL ans = 0;
    while(k > 0) {
        ans += bit[k];
        k -= (k & -k);
    }
    return ans;
}

void add(LL *bit, LL k, LL add)
{
    while(k <= n) {
        bit[k] += add;
        k += (k & -k);
    }
}

int main()
{
    LL l, r, w;
    while(~scanf("%lld%lld", &n, &m)) {
        mem0(bit0);
        mem0(bit1);
        a[0] = 0;
        for(int i = 1; i <= n; i ++) {
            scanf("%lld", &a[i]);
            add(bit0, i, a[i] - a[i-1]);
            add(bit1, i, (i-1)*(a[i] - a[i-1]));
        }
        while(m --) {
            scanf("%s", str);
            if(str[0] == 'C') {
                scanf("%lld%lld%lld", &l, &r, &w);
                add(bit0, l, w);
                add(bit0, r+1, -w);
                add(bit1, l, (l-1)*w);
                add(bit1, r+1, -r*w);
            }else {
                scanf("%lld%lld", &l, &r);
                LL ans = 0;
                ans -= (l-1)*sum(bit0,l-1)-sum(bit1,l-1);
			    ans += r*sum(bit0,r)-sum(bit1,r);
                printf("%lld\n", ans);
            }
        }
    }
    return 0;
}

总结:个人觉得树状数组的主要思想就是前缀和+差分思想

看了所有树状数组的代码,相比之下,线段树的代码是不是就显得格外的长,还容易出错,下面贴出最后一个例题的线段树AC的代码,大家比较下就。。。
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<math.h>
#include<time.h>
#include<map>
#include<string>
#include<algorithm>
#include<set>
#define N 50000

using namespace std;

int a;

struct node
{
    int L;
    int R;
    long long num;
    long long lazy;
    int lenth;
}leaves[100000<<2];

void Push_Tree(int k)
{
    if(leaves[k].lazy)
    {
        leaves[2*k].num = leaves[2*k].num + leaves[k].lazy*leaves[2*k].lenth;
        leaves[2*k+1].num = leaves[2*k+1].num + leaves[k].lazy*leaves[2*k+1].lenth;
        leaves[2*k].lazy += leaves[k].lazy;
        leaves[2*k+1].lazy += leaves[k].lazy;
        leaves[k].lazy = 0;
    }
}

void Build_Tree(int l, int r, int k)
{
    leaves[k].L = l;
    leaves[k].R = r;
    leaves[k].lazy = 0;
    leaves[k].lenth = r - l + 1;
    if(l == r){
        scanf("%lld", &leaves[k].num);
        return;
    }
    int mid = (l+r)/2;
    Build_Tree(l, mid, 2*k);
    Build_Tree(mid+1, r, 2*k+1);
    leaves[k].num = leaves[2*k].num+leaves[2*k+1].num;
}

void Update_Tree(int l, int r, int add, int k)
{
    if(leaves[k].L == l && leaves[k].R == r){
        leaves[k].num += leaves[k].lenth * add;
        leaves[k].lazy += add;
        return;
    }
    Push_Tree(k);
    int mid = (leaves[k].L+leaves[k].R)/2;
    if(r <= mid) Update_Tree(l, r, add, 2*k);
    else if(l > mid)Update_Tree(l, r, add, 2*k+1);
    else{
        Update_Tree(l, mid, add, 2*k);
        Update_Tree(mid+1, r, add, 2*k+1);
    }
    leaves[k].num = leaves[2*k].num + leaves[2*k+1].num;
}

long long Search_Tree(int l, int r, int k)
{
    if(leaves[k].L == l && leaves[k].R == r){
        return leaves[k].num;
    }
    Push_Tree(k);
    int mid = (leaves[k].L+leaves[k].R)/2;
    if(r <= mid) return Search_Tree(l, r, 2*k);
    else if(l > mid) return Search_Tree(l, r, 2*k+1);
    else{
        return Search_Tree(l, mid, 2*k) + Search_Tree(mid+1, r, 2*k+1);
    }
}

int main()
{
    int n, m, x, y, s;
    char oder[2];
    scanf("%d%d", &n, &m);
    Build_Tree(1, n, 1);
    while(m--){
        scanf("%s", oder);
        if(oder[0] == 'C'){
            scanf("%d%d%d", &x, &y, &s);
            Update_Tree(x, y, s, 1);
        }
        if(oder[0] == 'Q'){
            scanf("%d%d", &x, &y);
            printf("%lld\n", Search_Tree(x, y, 1));
        }
    }
    return 0;
}


相关标签: ACM 数据结构