洛谷OJ P2846 LJJ的数学课

题目链接：传送门

题目大意：略

题目思路：线段树or树状数组

　　　　　我们可以将区间值做一些调整。a*3+b*2+c=a+(a+b)+(a+b+c)

　　　　　也就是利用前缀和建树。然后单点更新也就转换成了区间更新。修改一个点x时，需要修改 x~n 的值（因为是按前缀和建树

　　　　　查询时也很简单，查询 x~y，则直接返回 x~y的值，再减去 （x-1的值）*（y-x+1），要把（1~x）的前缀和减去。

　　　　　用线段树时要注意一个坑点，若查询时 x==1，则不用减去任何值直接输出即可，否则有可能RE（别问我怎么知道的

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <cstring>

#include <stack>

#include <cctype>

 #include <queue>

#include <string>

#include <vector>

#include <set>

#include <map>

#include <climits>

#define lson rt<<1,l,mid

#define rson rt<<1|1,mid+1,r   ///宏

#define fi first

#define se second

#define ping(x,y) ((x-y)*(x-y))

#define mst(x,y) memset(x,y,sizeof(x))

#define mcp(x,y) memcpy(x,y,sizeof(y))

using namespace std;

#define gamma 0.5772156649015328606065120

#define MOD 1000000007

#define inf 0x3f3f3f3f

#define N 1000005

#define maxn 100005

typedef pair<int,int> PII;

typedef long long LL;

int n,m,k,cnt,L,R;

LL a[maxn],mrk[maxn<<],v;

struct Node{

    int l,r;

    LL v;

}node[maxn<<];

void build(int rt,int l,int r){

    node[rt].l=l;node[rt].r=r;

    if(l==r){

        node[rt].v=a[l];

        return;

    }

    int mid=l+r>>;

    build(lson);

    build(rson);

    node[rt].v=node[rt<<].v+node[rt<<|].v;

}

inline void pushup(int rt){

    int t=rt<<;

    mrk[t]+=mrk[rt];

    mrk[t|]+=mrk[rt];

    node[t].v+=mrk[rt]*(node[t].r-node[t].l+);

    node[t|].v+=mrk[rt]*(node[t|].r-node[t|].l+);

    mrk[rt]=;

}

void add(int rt,int l,int r){

    if(L<=l&&r<=R){

        node[rt].v+=v*(r-l+);

        mrk[rt]+=v;

        return;

    }

    if(mrk[rt])pushup(rt);

    int mid=l+r>>;

    if(R<=mid)add(lson);

    else if(L>mid)add(rson);

    else add(lson),add(rson);

    node[rt].v=node[rt<<].v+node[rt<<|].v;

}

LL get(int rt,int l,int r){

    if(L<=l&&r<=R) return node[rt].v;

    int mid=l+r>>;

    if(mrk[rt])pushup(rt);

    if(R<=mid)return get(lson);

    else if(L>mid)return get(rson);

    else return get(lson)+get(rson);

}

int main(){

    int i,j,x,y;

    scanf("%d%d",&n,&m);

    for(i=;i<=n;++i){

        scanf("%lld",&a[i]);

        a[i]+=a[i-];

    }

    build(,,n);

    while(m--){

        scanf("%d%d%lld",&y,&x,&v);

        if(y==){

            L=x;R=n;

            add(,,n);

        }

        else{

            L=x;R=(int)v;

            LL ans=get(,,n);

            if(x>){

                L=x-;R=x-;

                ans-=get(,,n)*(v-x+);

            }

            printf("%lld\n",ans);

        }

    }

    return ;

}

再附上树状数组代码

#include <cstdio>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

using namespace std;

const int N=;

typedef long long ll;

ll c[][N];

int n;

void add(int p,int x,ll y){while(x<=n){c[p][x]+=y;x+=x&-x;}}

ll query(int p,int x){ll r=;while(x){r+=c[p][x];x-=x&-x;}return r;}

int main(){

    int q,i,ty;

    ll x,y,ans;

    scanf("%d %d",&n,&q);

    for(i=;i<=n;i++){

        scanf("%lld",&x);

        add(,i,x);

        add(,i,i*x);

    }

    for(i=;i<=q;i++){

        scanf("%d %lld %lld",&ty,&x,&y);

        if(ty==){

            add(,x,y);

            add(,x,x*y);

        }

        else{

            ans=(y+)*(query(,y)-query(,x-))-(query(,y)-query(,x-));

            printf("%lld\n",ans);

        }

    }

    return ;

}