POJ 3468 A Simple Problem with Integers(树状数组区间修改+区间查询)
昨天看了一上午没看懂的题,今天上午终于解决了~~~
看了一位大神的博客,感觉清晰很多啊。
这个知识点感觉有套路可循,难道这就是模板??
(转自http://www.cnblogs.com/lcf-2000/p/5866170.html)
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 100005
long long c1[maxn]={0};
long long c2[maxn]={0};
int n,q,x,y,z;
char action;
long long a[maxn],s[maxn];
int lowbit(int x)
{
return x&(-x);
}
void add(int x,long long y)//给差分数组中的位置x增加y(差分数组c1[],c2[]初始值为0!)
{ int i;
for(i=x;i<=n;i+=lowbit(i))
{c1[i]+=y;
c2[i]+=(long long)y*x;}
}
void adde(int x,int y)//给原数组中的位置x增加y,即把原数组各项初始化
{
while(x<=n)
{
s[x]+=y;
x+=lowbit(x);
}
}
long long sum(int x)//查询前x项的和,这里表示前x项的总增量!,因为c1[],c2[]初始值都为0,所以sum(int x)表示前x项的和即前x项增加的总和
{
long long ans=0;
for(int i=x;i;i-=lowbit(i)) ans+=(x+1)*c1[i]-c2[i];
return ans;
}
long long sume(int x)//查询原数组前x项的前缀和
{
long long res=0;
while(x)
{
res+=s[x];
x-=lowbit(x);
}
return res;
}
int main()
{
memset(s,0,sizeof(s));
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{scanf("%lld",&a[i]);
adde(i,a[i]);
}
while(q--)
{ long long answer=0;
getchar();
scanf("%c",&action);
if(action=='Q')
{ scanf("%d%d",&x,&y);
answer=sum(y)-sum(x-1)+sume(y)-sume(x-1);
printf("%lld\n",answer);
}
else
{
scanf("%d%d%d",&x,&y,&z);
add(x,z);
add(y+1,-z);
}
}
return 0;
}