首页 > 代码库 > 初识树状数组

初识树状数组

描述 Description

  输入一个数列A1,A2….An(1<=N<=100000),在数列上进行M(1<=M<=100000)次操作,操作有以下两种: (1) 格式为C I X,其中C为字符“C”,I和X(1<=I<=N,|X|<=10000)都是整数,表示把把a[I]改为X (2) 格式为Q L R,其中Q为字符“Q”,L和R表示询问区间为[L,R](1<=L<=R<=N),表示询问A[L]+…+A[R]的值。

输入格式 Input Format

   第一行输入N(1<=N<=100000),表述数列的长度; 接下来N行,每行一个整数(绝对值不超过10000)依次输入每个数; 接下来输入一个整数M(1<=M<=100000),表示操作数量,接下来M行,每行为C I X或者Q L R。

输出格式 Output Format

  对于每个Q L R 的操作输出答案。

样例输入 Sample Input

  5

  1 2 3 4 5

  3

  Q 2 3

  C 3 9

  Q 1 4

样例输出 Sample Output

  5 16

时间限制 Time Limitation

  1s

  首先感谢ysc为我们带来的树状数组ppt,闲话也不多说了,树状数组的定义百科上也有,我也不在描述;

  本来看到点修改的我其实很懵,因为代码是这样写的

void build(int i,int val){
    while(i<=n){
        c[i]+=val;
        i+=lowbit(i);
    }
}

  这是一步步向上修改根节点,然而我们看到题目描述是修改某点的值为什么,而不是加;

  其实很容易,只要将要修改的值减去原来的值,赋给val就能实现。

  代码很简单,要注意的是刚开始要建立c数组。

  

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#define lowbit(i) i&(-i)
using namespace std;
int n,m;
int a[100100];
int c[100100];
int ans;

void build(int i,int val){
    while(i<=n){
        c[i]+=val;
        i+=lowbit(i);
    }
}

int sum(int x){
    int temp=0;
    while(x>0){
        temp+=c[x];
        x-=lowbit(x);
    }
    return temp;
}

int main(){
    //freopen("a.txt","r",stdin);
    //freopen("b.txt","w",stdout);
    cin>>n;
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        build(i,a[i]);
    }
    //cout<<sum(4)<<endl;
    cin>>m;
    for(int i=1;i<=m;++i){
        char c;
        int x,y;
        cin>>c;
        if(c==C){
            scanf("%d%d",&x,&y);
            build(x,y-a[x]);
            a[x]=y;
        }
        else if(c==Q){
            scanf("%d%d",&x,&y);
            ans=sum(y)-sum(x-1);
            printf("%d\n",ans);
        }
    }
    //cout<<sum(4)<<endl;
    return 0;
}

 

初识树状数组