poj 3468

题意：给出[1,n]区间内每个点的数值，让你执行下面的操作:
      1. C a b w : 区间[a,b]上所有点的数值加上w。
      2. Q a b : 输出区间[a,b]上所有点的数值之和。

思路：经典线段树。静态建树，成段修改，区间求和。用普通的线段树去做肯定超时，因为成段修改的时候会是o(n)。关键在于用add记录对应区间内所有元素的增量，并对查询函数进行相应的修改。注意修改和查询的一个很关键的性质：区间[node[u].left,node[u].right]必定包含区间[left,right]。

 

#include<iostream>
using namespace std;
const int Max = 100050;

struct data
{
    int l, r;
    __int64 sum, add;      //  sum存储区间数值之和，add存储区间内所有数的增量。
}node[3*Max];
int num[Max];
__int64 ans;

int max(int a, int b)
{
    return a > b ? a : b;
}

int min(int a, int b)
{
    return a < b ? a : b;
}

void BuildTree(int left, int right, int u) //  建树。
{          
    node[u].l = left;
    node[u].r = right;
    node[u].add = 0;
    if(left== right)
        node[u].sum = num[left];
    else
	{
		BuildTree(left, (left+right)/2, 2*u);  
		BuildTree((left+right)/2+1, right, 2*u+1);   
		node[u].sum = node[2*u].sum + node[2*u+1].sum;
    }
}

void updata(int left, int right, int val, int u)
{     //  修改。
    if(node[u].l == left && node[u].r == right)
	{     
		//  情况1：两区间完全匹配，新增的值记录为区间的add。
        node[u].add += val;
        return;
    }
    node[u].sum += (right-left+1) * val;             
    //  情况2：区间要继续分割，大区间的sum加上小区间所有数值新增的总和。
    if(left <= node[2*u].r)
	{
        int r = min(right, node[2*u].r);             //  区间分割要考虑全面。
        updata(left, r, val, 2*u);
    }
    if(right >= node[2*u+1].l)
	{
        int l = max(left, node[2*u+1].l);          //  区间分割要考虑全面。
        updata(l, right, val, 2*u+1);
    }
}

void query(int left, int right, int u) //  查询。
{              
    ans += (right-left+1) * node[u].add;     //  先加上区间[left,right]记录在[node[i].l,node[i].r]的总增量。         
    if(node[u].l == left && node[u].r == right)       //  情况1：两区间完全匹配。
        ans += node[u].sum;
    else if(right <= node[2*u].r)                    //  情况2：小区间被大区间的左子区间包含。
        query(left, right, 2*u);
    else if(left >= node[2*u+1].l)                 //  情况3：小区间被大区间的右子区间包含。
        query(left, right, 2*u+1);
    else
	{                                             //  情况4：小区间被大区间的两个子区间分割。
        int mid = (node[u].l + node[u].r)/2;
        query(left, mid, 2*u);
        query(mid+1, right, 2*u+1);
    }
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)
        scanf("%d",&num[i]);
    getchar();         //   记得要回收回车号。
    BuildTree(1, n, 1);
    while(m--)
	{
        int a, b, w;
        char order;
        scanf("%c", &order);
        if(order == 'C')
		{
            scanf("%d%d%d", &a, &b, &w);
            updata(a, b, w, 1);
        }
        else if(order == 'Q')
		{
            scanf("%d%d", &a, &b);
            ans = 0;
            query(a, b, 1);
            printf("%I64d\n", ans);
        }
        getchar();
    }
    return 0;
}