（以“ 分类:线段树分类:块状数组分类:树形结构 ==摘要== {{信息题|线段树练习|http://www.codevs.cn/problem/1080/|1|100|数组不够大|9...”为内容创建页面） |
小 （→题解： 链接修正） |
||
| 第7行： | 第7行： | ||
==题解== | ==题解== | ||
*线段树/树状数组/块状数组裸题。这题就写树状数组(Binary Indexed Tree，BIT，二分索引树)吧。 | *线段树/树状数组/块状数组裸题。这题就写树状数组(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 |
==代码== | ==代码== | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| 线段树练习 | ★☆☆☆☆ | 答案正确 | 100 | 2015-2-4 17:10:36 | 数组不够大（90） |
数据结构，支持区间修改和求和。
| 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));
}
}
}
|
CloudLunar