POJ 3468 A Simple Problem with Integers

[線段樹]
開始覺得非遞迴線段樹根本HOLD :3

卡(a^1>>1)卡了頗久 Note: 養成習慣 "(a^1)"

O(NlgN)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define N 100010
#define LL long long
using namespace std;
//BST
LL a[N];
LL NodeCnt[N*4];
LL NodeSum[N*4];
LL NodeImp[N*4];
int n;int base;
void BuildTree()
{
        base=pow(2,ceil(log2(n)))-1;
        if(base>=(n-2))
                base=base*2+1;
        memset(NodeCnt,(LL)0,sizeof(NodeCnt));
        memset(NodeSum,(LL)0,sizeof(NodeSum));
        memset(NodeImp,(LL)0,sizeof(NodeImp));
        for(int lx=0;lx<n;lx++)
                for(int prc=base+lx+1;prc;prc>>=1)
                        NodeSum[prc]+=a[lx],NodeCnt[prc]++;
}
void Edit(int a,int b,LL c)
{
        for(a+=base-1,b+=base+1;a^b^1;a>>=1,b>>=1)
        {
                if(~a&1)
                {
                    NodeImp[a^1]+=c;
                    for(int prc=((a^1)>>1);prc;prc>>=1)
                       NodeSum[prc]+=c*NodeCnt[a^1];
                }
                if(b&1)
                {
                    NodeImp[b^1]+=c;
                    for(int prc=((b^1)>>1);prc;prc>>=1)
                       NodeSum[prc]+=c*NodeCnt[b^1];
                }
        }
}
LL Ask(int a,int b)
{
        LL ret=0;
        for(a+=base-1,b+=base+1;a^b^1;a>>=1,b>>=1)
        {
                if(~a&1)
                {
                    ret+=NodeSum[a^1];
                    for(int prc=a^1;prc;prc>>=1)
                       ret+=NodeImp[prc]*NodeCnt[a^1];
                }
                if(b&1)
                {
                    ret+=NodeSum[b^1];
                    for(int prc=b^1;prc;prc>>=1)
                       ret+=NodeImp[prc]*NodeCnt[b^1];
                }
        }
        return ret;
}

int main()
{
        int Qs;
        while(scanf("%d %d",&n,&Qs)!=EOF)
        {
            memset(a,(LL)0,sizeof(a));
                for(int lx=0;lx<n;lx++)
                        scanf("%I64d",&a[lx]);
                BuildTree();
                int p,q;
                LL r;
                char c[100];
                while(Qs--)
                {
                        scanf("\n%c ",c);
                        if(c[0]=='Q')
                        {
                                scanf("%d %d",&p,&q);
                                printf("%I64d\n",Ask(p,q));
                        }
                        else
                        {
                                scanf("%d %d %I64d",&p,&q,&r);
                                Edit(p,q,r);
                        }
                }
        }
        return 0;
}