codevs1082 线段树练习3

题目

http://codevs.cn/problem/1082/

题解

线段树模板没什么好说的，下面贴一个树状数组解法

http://blog.csdn.net/fsahfgsadhsakndas/article/details/52650026

修改区间[l,r]后查询 i( l<= i<= r)：

c[l]+=x;
s[l]+=(l-1)*x;

则i点的值会改变 (i-(l-1))*x

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define N 200050 
#define ll long long
using namespace std;

int n,m,a[N];
ll c[N],c_1[N],c_2[N];//c_1[i]=a[i]-a[i-1];  c_2[i]=(i-1)*c_1[i]

int lowbit(int x)
{
    return x&(-x);
}

void update(ll *ar,int p,int x)
{
    while(p<=n)
    {
        ar[p]+=x;
        p+=lowbit(p);
    }
}

ll sum(ll *ar,int x)
{
    ll cnt=0;
    while(x)
    {
        cnt+=ar[x];
        x-=lowbit(x);
    }
    return cnt;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        update(c_1,i,a[i]-a[i-1]);
        update(c_2,i,(i-1)*(a[i]-a[i-1]));
    }
    scanf("%d",&m);
    while(m--)
    {
        int opt,a,b;scanf("%d%d%d",&opt,&a,&b);
        if(opt==1)
        {
            int x;scanf("%d",&x);
            update(c_1,a,x);update(c_1,b+1,-x);
            update(c_2,a,(a-1)*x);update(c_2,b+1,b*(-x));
        }
        else
        {
            ll sum1=(a-1)*sum(c_1,a-1)-sum(c_2,a-1);  
            ll sum2=b*sum(c_1,b)-sum(c_2,b);
            printf("%lld\n",sum2-sum1);  
        }
    }
    return 0;
}