poj 3468 A Simple Problem with Integers线段树区间修改

传送门 

题目意思很简单，有N个数，Q个操作，  Q l  r 表示查询从l到r 的和，C  l  r  v 表示将从l到r 的值加上v，明显的线段树，不知道线段树的人肯定暴力，肯定超时，哈哈！！

解题方法我在代码注释中写的很详细了

#include <stdio.h>
const int maxn = 100005;                      
typedef __int64 ll;                           //Hint  The sums may exceed the range of 32-bit integers.
int a[maxn];

struct node                                   //比较复杂的线段树都需要保存一个节点的多个信息，虽然
{                                             //可以使用多个数组来存储，但我个人不推荐这种做法
    int l, r, m;
    ll sum, mark;
}tree[maxn<<2];                               // << 这里使用位运算，位运算的效率要比* /运算的效率高
                                              //推荐大家在乘除2或2的某次方的时候使用位运算，

void build(int l, int r, int o)               //建树比较好理解，确定每个节点的各项，然后递归创建左右子树
{
    tree[o].l = l;
    tree[o].r = r;
    int m = (l+r)>>1;
    tree[o].m = m;
    tree[o].mark = 0;                         //mark的值一定要初始化为0，很重要
    if (l == r)                               //递归边界
    {
        tree[o].sum = a[l];
        return;
    }
    build(l, m, o<<1);
    build(m+1, r, (o<<1)+1);
    tree[o].sum = tree[o<<1].sum + tree[(o<<1)+1].sum;  //这里tree[(o<<1)+1] （o<<1） 我打了括号，以为位运算的优先级比+低
 }                                                      //不注意很容易出问题的

 void update(int l, int r, int v, int o)
 {
     if (tree[o].l == l && tree[o].r == r)
     {
        tree[o].mark += v;                              //在每次更新某段的时候我们还要我们标记这一段被加了v
        return;
     }
     tree[o].sum += (ll)(r-l+1)*v;
     if (tree[o].m >= r)                                //递归更新，无外乎三种情况    
        update(l, r, v, o<<1);
     else if (l > tree[o].m)
        update(l, r, v, (o<<1)+1);
     else
     {
         update(l, tree[o].m, v, o<<1);
         update(tree[o].m+1, r, v, (o<<1)+1);
     }
 }

ll query(int l, int r, int o)                                         
 {
     if (tree[o].l == l && tree[o].r == r)                           //我们也使用递归的方式查询，这是递归边界
        return tree[o].sum + tree[o].mark*(r-l+1);
     if (tree[o].mark != 0)
     {
         tree[o<<1].mark += tree[o].mark;                            //在查询的时候我将节点的mark值传递给子节点
         tree[(o<<1)+1].mark += tree[o].mark;
         tree[o].sum += (ll)(tree[o].r -tree[o].l +1)*tree[o].mark;  //并更新sum的值
         tree[o].mark = 0;
     }
     if (tree[o].m >= r)                                             //查询的三种情况
        return query(l, r, o<<1);
     else if (tree[o].m <l)
        return query(l, r, (o<<1)+1);
     else
        return query(l, tree[o].m, o<<1) + query(tree[o].m+1, r, (o<<1)+1);
 }

int main()
{
    int n, q;
    while (scanf("%d%d",&n,&q) != EOF)
    {
        for(int i = 1; i <= n; i++)
            scanf("%d",&a[i]);
        build(1, n, 1);
        char com;
        int l, r, v;
        while (q--)
        {
            getchar();
            scanf("%c",&com);
            if (com == 'Q')
            {
                scanf("%d%d",&l, &r);
                printf("%I64d\n",query(l,r,1));
            }
            else
            {
                scanf("%d%d%d",&l ,&r ,&v);
                update(l, r, v, 1);
            }
        }
    }
    return 0;
}