POJ3468：A Simple Problem with Integers （线段树||树状数组||Splay解决基本问题的效率对比）

You have N integers, A₁, A₂, ... , A_N. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A₁, A₂, ... , A_N. -1000000000 ≤ A_i ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of A_a, A_a₊₁, ... , A_b. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of A_a, A_a₊₁, ... , A_b.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

Input

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

题意：就是区间更改，区间求和。

思路：常规线段树，也可以树状态数组，也可以splay。

ps：我记得csl蔡神就是经常用splay来做线段树题，我最近发现这真是个好习惯。很大的好处就是写平衡树可以写得很灵活吧。

这里主要是都写一下，然后对比下效率。也尽量以后多写splay。）

体会：由于splay基本操作后都要把Now节点splay到根节点，可以从这里想办法优化。

比如，不要求在线的时候（比如区间第K大），可以向莫队一样，排序后再回答，这样，每次splay的高度会小一些。

其他优化就待续了，目前平衡树做得少。

树状数组：1969ms：

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=100010;
ll a[maxn],b[maxn],c[maxn];
char opt[5];int n,m;
int lowbit(int x) {return x&(-x);}
void add(ll *bb,ll *cc,int x,int val)
{
    ll tmp=x*val;
    for(int i=x;i<=n+1;i+=lowbit(i)) 
      bb[i]+=val,cc[i]+=tmp;
}
ll query(ll *bb,ll *cc,int x)
{
    ll res=0;
    for(int i=x;i;i-=lowbit(i)) res+=bb[i]; res*=(x+1);
    for(int i=x;i;i-=lowbit(i)) res-=cc[i];
    return res+a[x];
}
int main()
{
    while(~scanf("%d%d",&n,&m)){
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]),a[i]+=a[i-1];
        for(int i=1;i<=n;i++) b[i]=c[i]=0;
        while(m--){
            scanf("%s",opt); int x,y,z;
            if(opt[0]=='Q')scanf("%d%d",&x,&y),printf("%lld
",query(b,c,y)-query(b,c,x-1));
            else scanf("%d%d%d",&x,&y,&z),add(b,c,x,z),add(b,c,y+1,-z);
        }
    } return 0;
}

线段树：2407ms：

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int maxn=100010;
int n,m;int a[maxn];
struct TREE
{
    ll sum[maxn<<2];int lazy[maxn<<2];
    void build(int Now,int l,int r)
    {
        lazy[Now]=0;
        if(l==r) { sum[Now]=a[l]; return;}
        int Mid=(l+r)>>1;
        build(Now<<1,l,Mid);
        build(Now<<1|1,Mid+1,r);
        pushup(Now);
    }
    void add(int Now,int l,int r,int x,int y,int val)
    {
        if(x<=l&&y>=r) { sum[Now]+=(ll)(r-l+1)*val;lazy[Now]+=val; return ;}
        pushdown(Now,l,r);  int Mid=(l+r)>>1;
        if(y<=Mid) add(Now<<1,l,Mid,x,y,val);
        else if(x>Mid) add(Now<<1|1,Mid+1,r,x,y,val);
        else add(Now<<1,l,Mid,x,Mid,val),add(Now<<1|1,Mid+1,r,Mid+1,y,val);
        pushup(Now);
     }
     ll query(int Now,int l,int r,int x,int y)
     {
        if(x<=l&&y>=r)  return sum[Now];
        pushdown(Now,l,r); int Mid=(l+r)>>1;
        if(y<=Mid) return query(Now<<1,l,Mid,x,y);
        else if(x>Mid) return query(Now<<1|1,Mid+1,r,x,y);
        else return query(Now<<1,l,Mid,x,Mid)+query(Now<<1|1,Mid+1,r,Mid+1,y);
        pushup(Now);
    }
    void pushup(int Now) { sum[Now]=sum[Now<<1]+sum[Now<<1|1];}
    void pushdown(int Now,int l,int r)
    {
        int Mid=(l+r)>>1;
        lazy[Now<<1]+=lazy[Now];sum[Now<<1]+=(ll)(Mid-l+1)*lazy[Now];
        lazy[Now<<1|1]+=lazy[Now];sum[Now<<1|1]+=(ll)(r-Mid)*lazy[Now];
        lazy[Now]=0;
    }
}Tree;
int main()
{
     while(~scanf("%d%d",&n,&m)){
         for(int i=1;i<=n;i++) scanf("%d",&a[i]);
         Tree.build(1,1,n);
         for(int i=1;i<=m;i++){
                char opt[5];int x,y,z;
                scanf("%s",opt);
                if(opt[0]=='Q') scanf("%d%d",&x,&y),printf("%lld
",Tree.query(1,1,n,x,y));
                else scanf("%d%d%d",&x,&y,&z),Tree.add(1,1,n,x,y,z);
         }
     } return 0;
}

splay：3891ms。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int maxn=100010;
int a[maxn];
struct Splay
{
    int ch[maxn][2],sz[maxn],fa[maxn],rt,cnt;
    ll sum[maxn],key[maxn],lazy[maxn];
    void init()
    {
        rt=cnt=0;
    }
    int get(int x)
    {
        return ch[fa[x]][1]==x;
    }
    void pushdown(int Now)
    {
        if(!lazy[Now]) return ;
        int cl=ch[Now][0],cr=ch[Now][1];
        if(cl){
             sum[cl]+=sz[cl]*lazy[Now];
             lazy[cl]+=lazy[Now]; key[cl]+=lazy[Now];
        }
        if(cr){
             sum[cr]+=sz[cr]*lazy[Now];
             lazy[cr]+=lazy[Now]; key[cr]+=lazy[Now];
        }
        lazy[Now]=0;
    }
    void update(int Now)
    {
        sum[Now]=key[Now]; sz[Now]=1;
        if(ch[Now][0]) sum[Now]+=sum[ch[Now][0]],sz[Now]+=sz[ch[Now][0]];
        if(ch[Now][1]) sum[Now]+=sum[ch[Now][1]],sz[Now]+=sz[ch[Now][1]];
    }
    void rotate(int x)
    {
        int old=fa[x],fold=fa[old],opt=(ch[old][1]==x);
        pushdown(old); pushdown(x);
        fa[ch[x][opt^1]]=old; ch[old][opt]=ch[x][opt^1];
        ch[x][opt^1]=old; fa[old]=x; fa[x]=fold;
        if(!fold) rt=x;
        else ch[fold][ch[fold][1]==old]=x;
        update(old); update(x);
    }
    void splay(int x,int y)
    {
        for(int f;(f=fa[x])!=y;rotate(x)){
            if(fa[f]!=y) 
               rotate(get(x)==get(f)?f:x);
        }
        if(!y) rt=x;
    }
    int build(int L,int R)
    {
        if(L>R) return -1;
        int Mid=(L+R)>>1;
        if(!rt) rt=Mid;
        key[Mid]=a[Mid]; sum[Mid]=a[Mid]; sz[Mid]=1;
        lazy[Mid]=fa[Mid]=ch[Mid][0]=ch[Mid][1]=0;
        int cl=build(L,Mid-1);
        if(cl!=-1) {
            ch[Mid][0]=cl; fa[cl]=Mid; sz[Mid]+=sz[cl];
        } 
        int cr=build(Mid+1,R);
        if(cr!=-1){
            ch[Mid][1]=cr; fa[cr]=Mid; sz[Mid]+=sz[cr];
        }
        update(Mid);
        return Mid;
    }
    ll query(int x,int y)
    {
        splay(x,0); splay(y,x);
        return sum[ch[ch[rt][1]][0]];
    }
    void change(int x,int y,int z)
    {    
        splay(x,0); splay(y,x);
        int t=ch[ch[rt][1]][0];
        key[t]+=z; lazy[t]+=z;
        sum[t]+=sz[t]*z;
    }
}S;
int main()
{
    int N,Q,x,y,z; char opt[3];
    while(~scanf("%d%d",&N,&Q)){
        S.init();
        for(int i=1;i<=N;i++) scanf("%d",&a[i+1]); a[1]=a[N+2]=0;
        S.build(1,N+2);
        while(Q--){
            scanf("%s",opt);
            if(opt[0]=='C'){
                scanf("%d%d%d",&x,&y,&z);
                S.change(x,y+2,z);
            }
            else {
                scanf("%d%d",&x,&y);
                printf("%lld
",S.query(x,y+2));
            }
        }
    }
    return 0;
}