题目描述:

已知一个数列,你需要进行下面两种操作:

  1. 将某一个数加上x
  2. 求出某区间每一个数的和

先说说什么是树状数组

这是(如下图)一个由二叉树变形而来的图像

我们称每个 端节点 为 C[i],代表着其两个子节点权重的和

eg.C[1]=A[1],C[2]=A[1]+A[2],C[3]=A[3] etc.

我们可以发现:如果将i写成对应的二进制,设k为其二进制从最低位开始向左至最后一个连续的0的长度

eg.k(10110)=1,k(1101000)=3 etc.

那么我们可以得到:

C[(1)]=A[(1)]
C[(10)]=A[(1)]+A[(10)]
C[(11)]=A[(11)]
...
C[(110)]=A[(101)]+A[(110)]
...

=>C[i]=A[i-2^k+1]+A[i-2^k+2]+…+A[i]

那么操作空间就有了

我们先定义一个求k的函数 lowbit(k):

int lowbit(int k){
/*
    -a为a的补码
    即a每二进制位取反后,整体+1 
    a&(-a)即为a中最低位1的位置(2^k) 
*/
    return k&(-k);
}

此函数的输出为 2^k,那么 => C[i]=A[i-lowbit(i)+1]+A[i-lowbit(i)+2]+…+A[i]

接下来是查询tree[1-x]区间内的和(此处tree[]即为C[]):

根据公式sum(x)=A[1]+A[2]+A[3]+…+A[x]=C[x]+C[x-lowbit(x)]+C[x-lowbit(x)-lowbit(x-lowbit(x))]+…+C[m-lowbit(m)] (m-lowbit(m)=lowbit(m-lowbit(m)))

可得:

int sum(int x){
    int ans=0;
    while(x/*即x>0*/){
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}

那我们需要修改A[i]时,应该如何操作呢

再拿出之前的图

可以看见,当更新了A[i]时,即需要更新 C[i],C[i+lowbit(i)],C[i+lowbit(i)+lowbit(i+lowbit(i))],…,C[x] (x<=n,n为输入数据数)

void add(int x,int k){
    while(x<=n){
        tree[x]+=k;
        x+=lowbit(x);
    }
}

那么我们可以得到完整的代码 等一下

之前说了,sum(x)得到的是tree[1-x]区间内的和,那怎么得到tree[a-b]的和呢

简单

sum_of(tree[a-b])=sum[b]-sum[a-1]

那么现在我们可以得到完整的代码了

/**
   *	  树状数组
   *----------------------------------
   *   Author: Eduarte
   *   Email: i@oxdl.cn
   *   Website:https://oxdl.cn?p=269
   *----------------------------------
   *   Date: 2018/12/30
   *   Version: 1.0
   */

//此题目在线测评地址:https://www.luogu.org/problemnew/show/P3374
#include <iostream>
#include <cstdio>

#define maxn 10000000

int n,m,tree[maxn];

int lowbit(int k){
/*     
    -a为a的补码     
    即a每二进制位取反后,整体+1      
    a&(-a)即为a中最低位1的位置(2^k)  
*/
    return k&(-k);
}

void add(int x,int k){
    while(x<=n){
        tree[x]+=k;
        x+=lowbit(x);
    }
}
    
int sum(int x){ 
    int ans=0; 
    while(x/*即x>0*/){ 
        ans += tree[x]; 
        x -= lowbit(x); 
    } 
    return ans; 
}

int main(){
    std::cin>>n>>m;
    int a,b,c;
    for(int i=1;i<=n;i++){
        std::cin>>a;
        add(i,a);
    }
    for(int i=1;i<=m;i++){
        std::cin>>a>>b>>c;
        if(a&1){
            add(b,c);
        }
        else{
            std::cout<<sum(c)-sum(b-1)<<std::endl;
        }
    }
}

测试数据:

5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4

输出:

14
16
打赏 赞(1)
支付宝二维码图片

支付宝扫描二维码打赏

1 对 “树状数组的原理与实现”的想法;

发表评论

电子邮件地址不会被公开。

Scroll Up