摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 失误原因(初次提交分数)
线段树练习 ★☆☆☆☆ 答案正确 100 2015-2-4 17:10:36 数组不够大(90)

题意

数据结构,支持区间修改和求和。

题解

  • 线段树/树状数组/块状数组裸题。这题就写树状数组(Binary Indexed Tree,BIT,二分索引树)吧。
    • 树状数组的原理:参阅http://blog.csdn.net/int64ago/article/details/7429868
    • 树状数组的实现:参阅维基百科http://zh.wikipedia.org/wiki/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84

代码

1080.cpp代码已折叠
展开折叠内容
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
template<size_t N,typename T=int>
class BIT
{
private:
    T bit[N];
    const int Lowbit(const int &x)
    {
        return x&(-x);
    }
public:
    size_t n;
    T a[N];
    void Build()
    {
        for(int i=1;i<=n;++i)
        {
            bit[i]=a[i];
            for(int j=i-1;j>i-Lowbit(i);j-=Lowbit(j))
                bit[i]+=bit[j];
        }
    }
    void Update(const int i,const int _delta)
    {
        a[i]+=_delta;
        for(int j=i;j<=n;j+=Lowbit(j))
                bit[j]+=_delta;
    }
    const T GetSum(const int &k)
    {
        T ans(0);
        for(int i=k;i>0;i-=Lowbit(i))
        {
            ans+=bit[i];
        }
        return ans;
    }
    const T GetSum(const int &l,const int &r)
    {
        return GetSum(r)-GetSum(l-1);
    }
};
BIT<1000000,int> bit;
int main()
{
    scanf("%d",&bit.n);
    for(int i=1;i<=bit.n;++i)
    {
        scanf("%d",&bit.a[i]);
    }
    bit.Build();
    int m;
    scanf("%d",&m);
    for(int i=1,a,b,c;i<=m;++i)
    {
        scanf("%d%d%d",&a,&b,&c);
        if(a==1)
        {
            bit.Update(b,c);
        }
        else
        {
            printf("%d\n",bit.GetSum(b,c));
        }
    }
}

著作权声明[编辑]

关于[编辑]