树状数组（单点+区间的所有操作）

程序员文章站 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;
}

树状数组（单点+区间的所有操作）

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

单点更新+区间求和

1、基于线段树的实现

2、BIT结构：

3、BIT求和

4、BIT的更新

区间更新+单点求值（基于单点更新+区间求和）

区间更新+区间求和（基于区间更新+单点求和）还是差分的思想，重点！

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

hdu 1754 I Hate It (树状数组求区间最大和)（线段树单点修改）

树状数组（单点+区间的所有操作）

树状数组：单点修改，区间查询（详解）

树状数组进阶（区间修改+单点查询）

求数组中区间中最小数*区间所有数和的最大值

把$input_arr进行组合操作，并返回一个包含所有组合的数组

把$input_arr进行组合操作，并返回一个包含所有组合的数组

树状数组(区间,单点间操作)

【树状数组】普通、二维、离线树状数组的(单点修改，单点查询，区间修改，区间查询)模板及应用总结

PHP数组操作之计算数组所有元素和的方法