POJ 3468 A Simple Problem with Integers 线段树

解题思路:

标准的区间更新。

树节点如果只存和会导致每次加数的时候都要更新到叶子节点，速度太慢(O(nlogn)) ，

所以树节点应该存原来初始的和nsum和当刚好是这段区间所累加的和lnc。本节点区间的和实际上是nsum+lnc*(R-L+1)。

每次插入将路过的节点中的nsum加上插入的c*(r-l+1)，直到刚好到要插入的区间将c累加到lnc中。

每次查询路过的区间就将(r-l+1)*lnc累加到ans上。

  1 #include <iostream>
  2 #include <cstdio>
  3 using namespace std;
  4 struct cnode
  5 {
  6     int l,r;
  7     cnode *pl,*pr;
  8     long long nsum;
  9     long long lnc;
 10     int mid()
 11     {
 12         return (l+r)/2;
 13     }
 14 };
 15 cnode t[200010];
 16 int ncount=0;
 17 long long ans;
 18 void build(cnode *proot,int l,int r)
 19 {
 20     proot->l=l;
 21     proot->r=r;
 22     proot->nsum=0;
 23     proot->lnc=0;
 24     if(l==r) return;
 25     ncount++;
 26     proot->pl=t+ncount;
 27     ncount++;
 28     proot->pr=t+ncount;
 29     build(proot->pl,l,(l+r)/2);
 30     build(proot->pr,(l+r)/2+1,r);
 31 }
 32 void insert(cnode *proot,int i,int v)
 33 {
 34     proot->nsum+=v;
 35     if(proot->l==i&&proot->r==i)
 36         return;
 37     if(i<=proot->mid())
 38         insert(proot->pl,i,v);
 39     else
 40         insert(proot->pr,i,v);
 41 }
 42 void add(cnode *proot,int a,int b,long long c)
 43 {
 44     if(proot->l==a&&proot->r==b)
 45     {
 46         proot->lnc+=c;
 47         return;
 48     }
 49     proot->nsum+=c*(b-a+1);
 50     if(b<=proot->mid())
 51         add(proot->pl,a,b,c);
 52     else if(a>=proot->mid()+1)
 53         add(proot->pr,a,b,c);
 54     else
 55     {
 56         add(proot->pl,a,proot->mid(),c);
 57         add(proot->pr,proot->mid()+1,b,c);
 58     }
 59 }
 60 void query(cnode *proot,int a,int b)
 61 {
 62     ans+=(b-a+1)*(proot->lnc);
 63     if(proot->l==a&&proot->r==b)
 64     {
 65         ans+=proot->nsum;
 66         return;
 67     }
 68     if(b<=proot->mid())
 69          query(proot->pl,a,b);
 70     else if(a>=proot->mid()+1)
 71          query(proot->pr,a,b);
 72     else
 73     {
 74          query(proot->pl,a,proot->mid());
 75          query(proot->pr,proot->mid()+1,b);
 76     }
 77 }
 78 
 79 
 80 int main()
 81 {
 82     int n,q,a,b,c;
 83     scanf("%d%d",&n,&q);
 84     build(t,1,n);
 85     for(int i=1;i<=n;i++)
 86     {
 87         scanf("%d",&a);
 88         insert(t,i,a);
 89     }
 90     char str[10];
 91     for(int i=0;i<q;i++)
 92     {
 93         scanf("%s",str);
 94         if(str[0]=='C')
 95         {
 96             scanf("%d%d%d",&a,&b,&c);
 97             add(t,a,b,c);
 98         }
 99         else
100         {
101             scanf("%d%d",&a,&b);
102             ans=0;
103             query(t,a,b);
104             printf("%lld
",ans);
105         }
106     }
107 }