已知一个数列,你需要进行下面两种操作:
1.将某一个数加上x
2.求出某区间每一个数的和
树状数组是依靠位运算的一种数据结构。
狭义来说是用来求前缀和的…… 然而我们知道如果 (f[i]) 表示 原序列前(i)项的和,那么 (f[j]-f[i-1]) 就是 原序列 (i...j) 的和
这样一个东西:
求前缀和的时候,我们希望将一个前缀分为一些子集的和。
下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | ... |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
内容 | 1 | 1...2 | 3 | 1...4 | 5 | 5...6 | 7 | 1...8 | 9 | 9...10 | 11 | 9..12 | ... |
然后就可以通过某种玄学的跳跃来求和啦
#include <iostream>
using namespace std;
int n,c[50000005]={};
int lowbit(int a)
{ return a&-a; }
void add(int k,int x)
{
while (k<=n)
{
c[k]+=x;
k+=lowbit(k);
}
return;
}
int num(int xd)
{
int sum=0;
while (0<xd)
{
sum+=c[xd];
xd-=lowbit(xd);
}
return sum;
}
int section(int x,int y)
{
return num(x)-num(y-1);
}
int main()
{
int m;
cin>>n>>m;
for (int i=1;i<=n;i++)
{
int k;
cin>>k;
add(i,k);
}
for (int i=1;i<=m;i++)
{
int fl,x,y;
cin>>fl>>x>>y;
if (fl==1)//单点修改
{
add(x,y);
continue;
}
cout<<section(y,x);//区间求和
}
return 0;
}