首页 > 编程语言 > 详细

树状数组维护前缀和

时间:2019-05-08 00:35:11      阅读:188      评论:0      收藏:0      [点我收藏+]

树状数组是用来维护序列前缀和的数据结构。它的修改与求和都是O(logn)的,效率非常高。

我们设序列为A,则树状数组c中,c[i]记录序列A的区间[ i-lowbit(i)+1 , i ]中所有数的和。 (树状数组是个好东西ovo) 技术分享图片

树状数组在进行区间操作时,要从上到下访问,进行单点操作时,要从下到上访问。 

树状数组维护序列前缀和的模版如下:

 

#include <iostream>
#include <cstdio>
#define maxn 500005
using namespace std;

int n,m;
int c[maxn];//c[i]存序列a中i-lowbit(i)+1到i的所有数的和(树状数组)

int read()
{
    int f=1,x=0;
    char ch;
    while(ch<0||ch>9)
    {
        if(ch==-)f=-1;
        ch=getchar();
    }
    while(ch>=0&&ch<=9)
    {
        x=x*10+ch-0;
        ch=getchar();
    }
    return f*x;
}

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

void update(int x,int y)
{
    while(x<=n)
    {
        c[x]+=y;
        x+=lowbit(x);
    }
}//将序列a[x]加上y

int sum(int x)
{
    int res=0;
    while(x>0)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}//求序列1-x的和

int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
    {
        //a[i]=read();
        int v=read();
        update(i,v);
    }
    for(int i=1;i<=m;i++)
    {
        int op,x,y;
        op=read();x=read();y=read();
        if(op==1)
        {
            update(x,y);
        }
        if(op==2)
        {
            int ans=sum(y)-sum(x-1);
            printf("%d\n",ans);
        }
    }

    return 0;
}

 

树状数组维护前缀和

原文:https://www.cnblogs.com/Bw-Orzzzzz/p/10829093.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!