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