求助。关于用树状数组模拟【区间增减】【区间求和】的问题。

我是这样子做的，可是在WIKIOI上总是WA：
a[i]是原数列
b[i]是差分了一下，即b[i]=a[i]-a[i-1];
c[i]是维护b[i]前缀和的
d[i]是维护[i]*b[i]的前缀和的。
显然S(a[i])=a[1]+a[2]+...+a[n]=b[1]+(b[1]+b[2])+(b[1]+b[2]+b[3])+...+(b[1]+b[2]+...+b[n])=(n-1)*(b[1]+...+b[n])-(1*b[1]+2*b[2]+...+n*b[n])=（n-1)*S(c[n])-S(d[n]);
所以只要用c[i]维护b[i]前缀和，d[i]维护i*b[i]的前缀和就可以了吧。。
每次增减[l,r]只需要plus(l,w)和plus(r+1,-w)即可了吧。。
询问[l,r]之和即输出(r+1)*Sumc(r)-l*Sumc(l-1)-Sumd(r)+Sumd(l-1);即可了吧。。
-------------------------------------------------
所以求助各位，我的思路在哪里有问题么，或者我的代码（2L）有什么问题么。多谢救援！

#include <iostream>
using namespace std;
long long a[10086],n,c[10086],s[10086],b[10086],d[10086];
int Lowbit(int t)
{
return t & ( t ^ ( t - 1 ) );
}
long long Sum(int end)
{
long long sum = 0;
while (end > 0)
{
sum += c[end];
end -= Lowbit(end);
}
return sum;
}
long long Sum2(int end)
{
long long sum = 0;
while (end > 0)
{
sum += d[end];
end -= Lowbit(end);
}
return sum;
}
void plusc(int pos,int num)
{
int qqq=1;
qqq=pos;
while(pos <= n)
{
c[pos] += num;
d[pos] += num*qqq;
pos += Lowbit(pos);
}
return;
}
int main()
{
a[0]=0;
b[0]=a[0];
c[0]=a[0];
s[0]=a[0];
d[0]=a[0];
for(int i=1;i<=n+10;i++)s[i]=0;
cin>>n;
for(int i=1;i<=n;i++){cin>>a[i];b[i]=a[i]-a[i-1];s[i]=s[i-1]+b[i];}
for(int i=1;i<=n;i++){c[i]=s[i]-s[i-Lowbit(i)];}
s[0]=a[0];
s[1]=a[1];
for(int i=2;i<=n;i++)s[i]=s[i-1]+i*b[i];
for(int i=1;i<=n;i++)d[i]=s[i]-s[i-Lowbit(i)];
// for(int i=1;i<=n;i++)cout<<a[i]<<'-'<<b[i]<<'-'<<c[i]<<'-'<<d[i]<<endl;
int p;
cin>>p;
int x,y,z,e;
long long k;
for(int i=1;i<=p;i++)
{
cin>>x;
if(x==1){cin>>y>>z>>e;plusc(y,e);plusc(z+1,-e);}
if(x==2){cin>>y>>z;k=(z+1)*Sum(z)-y*Sum(y-1)-Sum2(z)+Sum2(y-1);cout<<k<<endl;}
}
return 0;
}

不感兴趣

开通SVIP免广告

如果我没记错的话最终结果里的n-1应该是n+1

Orz 昨天在yy如何让树状数组支持段修改和段查询，没有yy出来，最后去打线段树了……
受教了

杨思雨 - 伸展树的基本操作与应用
Crash - 运用伸展树解决数列维护问题

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！

5回复贴，共1页

<<返回noip吧

分享到:

日	一	二	三	四	五	六