http://codevs.cn/problem/1082/
【AC】
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+;
int n;
ll a[maxn];
ll c1[maxn];
ll c2[maxn];
int lowbit(int x)
{
return x&-x;
}
void add(ll *c,int k,ll val)
{
while(k<=n){
c[k]+=val;
k+=lowbit(k);
}
}
ll query(ll *c,int k)
{
ll ans=;
while(k)
{
ans+=c[k];
k-=lowbit(k);
}
return ans;
}
ll solve(int x)
{
ll ans=;
ans+=x*query(c1,x);
ans-=query(c2,x);
return ans;
}
ll solve(int x,int y)
{
return solve(y)-solve(x-);
}
int main()
{
while(~scanf("%d",&n))
{
a[]=;
for(int i=;i<=n;i++)
{
scanf("%I64d",&a[i]);
// cout<<a[i]<<endl;
add(c1,i,a[i]-a[i-]);
add(c2,i,(i-)*(a[i]-a[i-]));
}
int q;
scanf("%d",&q);
int tp;
while(q--)
{
scanf("%d",&tp);
if(tp==)
{
int x,y;ll val;
scanf("%d%d%I64d",&x,&y,&val);
add(c1,x,val);
add(c1,y+,-val);
add(c2,x,1ll*(x-)*val);
add(c2,y+,-1ll*y*val);
}
else
{
int x,y;
scanf("%d%d",&x,&y);
ll ans=solve(x,y);
printf("%I64d\n",ans);
}
}
}
return ;
}
【原理】
原理是用了差分数组,转载自http://www.cnblogs.com/boceng/p/7222751.html
树状数组时间复杂度为O(MlogN), 实际用的时候优于线段树,且写得少。
神牛是引入了差分数组,要维护的差分数组ks[i] = a[i] - a[i-1]; 可以容易得到a[i] = ks[1] + ks[2] + ... + ks[i]; 即前i项和,为方便记为sigma(ks, i),已经可以看到树状数组的影子了,所以求区间和随之得到
a[1] + a[2] + .. + a[n] = sigma(ks, 1) + sigma(ks, 2) + ... + sigma(ks, n);
= n*ks[1] + (n-1)*ks[2] + ... + 2*ks[n-1] + 1*ks[n];
= n*(ks[1] + ks[2] +...+ ks[n]) - (0*ks[1] + 1*ks[2] + ... + (n-1)*ks[n]);
所以可以得到 sum[n] =n * sigma(ks, n) - (0*ks[1] + 1*ks[2] + ... + (n-1)*ks[n]);
令jk[i] = (i-1) * ks[i];
则 sum[n] = n * sigma(ks, n) - sigma(jk, n);
之后便是构造两个树状数组;
int lowbit(int k){
return k & -k;
}
void add(int n, int *c, int k, int va){
while(k <= n){
c[k] += va;
k += lowbit(k);
}
} //------------------------------------- for(i = ; i <= n; ++i){
add(n, c1, i, jk[i]-jk[i-]);
add(n, c2, i, (i-)*(jk[i]-jk[i-]));
}
然后进行查询求和
int sigma(int *c, int k){
int sum = ;
while(k){
sum += c[k];
k -= lowbit(k);
}
return sum;
}
int getSum(int s, int t){
return (t*sigma(c1, t)-sigma(c2, t)) - ((s-)*sigma(c1, s-)-sigma(c2, s-));
}
进行单点查询时,只需两个参数均传入该点。
在进行区间更新的时候,神牛市通过两次维护c1,两次c2得到的,但本人推测了几种情况,都不能很好的解释这么做的原因,
void update(int s, int t, int va){
add(c1, s, va);
add(c1, t+, -va);
add(c2, s, va*(s-));
add(c2, t+, -va*t);
}