#include<iostream>
#include<stdio.h>
using namespace std;

int n,q;
int ccount;
long long sum,sum1,sum2;
int num[1000000];
struct cnode{
       int l,r;
       cnode *left,*right;
       long long sum;
       long long Inc;
       }tree[3000000];

void buildtree(cnode *root,int l,int r)
{    root->l=l;
     root->r=r;
     root->Inc=0;
     if(l==r)
     { 
      root->sum=num[l];
      return;   
     }
      ccount++;
       root->left=tree+ccount;
       buildtree(root->left,l,(l+r)/2);    
       ccount++;
       root->right=tree+ccount;
       buildtree(root->right,(l+r)/2+1,r);
     root->sum=root->left->sum+root->right->sum;
} 
void add(cnode *root,int a,int b,long long c)
{
     if(root->l==a&&root->r==b)
      { root->Inc+=c;
        return;
       }
      root->sum+=c*(b-a+1);
      
     if(b<=(root->l+root->r)/2)
     add(root->left,a,b,c);
     else if(a>(root->l+root->r)/2)
      add(root->right,a,b,c);
     else 
     { add(root->left,a,(root->l+root->r)/2,c);
       add(root->right,(root->l+root->r)/2+1,b,c);
          }
     } 
long long query(cnode *root,int s,int v)
{ 
   if(root->l==s&&root->r==v)
   {
      root->sum+=root->Inc*(v-s+1);
    //  root->Inc=0;
      return root->sum;
                       
    }  
    
    root->sum+=(root->r-root->l+1)*root->Inc;
    add(root->left,root->l,(root->l+root->r)/2,root->Inc);
    add(root->right,(root->l+root->r)/2+1,root->r,root->Inc);    
    root->Inc=0; 
    if(v<=(root->l+root->r)/2)
     return query(root->left,s,v);
    else if(s>(root->l+root->r)/2)
     return query(root->right,s,v);
    else
    {  
       sum1=query(root->left,s,(root->l+root->r)/2);
        sum2=query(root->right,(root->l+root->r)/2+1,v);
       return sum1+sum2;        
    }
}
int main()
{   int a,b,d,e,s,v;
    char c[10];
   while(scanf("%d%d",&n,&q)!=EOF){
        ccount=0;
        for(int i=1;i<=n;i++)
         scanf("%d",&num[i]);
           
        buildtree(tree,1,n); 
        for(int j=0;j<q;j++)
        {
         scanf("%s",c);
         if(strcmp(c,"C")==0)
         { 
         scanf("%d%d%d",&b,&d,&e);
         add(tree,b,d,e);
                   }
         else if(strcmp(c,"Q")==0)
         {
          scanf("%d%d",&s,&v);
          printf("%I64d\n",query(tree,s,v));       
                   }
         }
  
}
    //system("pause");
    return 0;
}

• Re:提交了很多次都是wa，初学线性树，求大神指点 (2666) haining 2012-07-04 10:24:28