CodeVS/1080 2015年2月4日 (三) 17:10云璟月（讨论 | 贡献）的版本 (差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
线段树练习	★☆☆☆☆	答案正确	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)); } } }