【转】POJ 3468 A Simple Problem with Integers:线段树 简单操作 注意更新到区间而非叶节点

#include<cstdio>
#include<iostream>
using namespace std;
#define Size 100000

struct Node
{
        int L, R;
        long long Sum, Inc;
        int Mid()
        {
                return (L+R)/2;
        }
}Tree[Size*3];

void CreatTree( int root, int L, int R )// 建区间树
{
        Tree[root].L = L;
        Tree[root].R = R;
        Tree[root].Sum = 0;
        Tree[root].Inc = 0;

        if( L==R )
            return;

        CreatTree( root*2+1, L, (L+R)/2 );
        CreatTree( root*2+2, (L+R)/2+1, R );
}

void Insert( int root, int i, int  j )// 位置i 插入 j
{
        if( Tree[root].L == Tree[root].R )
        {
                Tree[root].Sum = j;
                return ;
        }

        Tree[root].Sum+=j;

        if( i<=Tree[root].Mid() )
            Insert( root*2+1, i, j );
        else
            Insert( root*2+2, i, j );

}

void Add( int  root, int s, int e, int j )// 区间[s, e] 上每个元素加j
{
        if( Tree[root].L==s && Tree[root].R==e )
        {
                Tree[root].Inc += j;
                return ;
        }

        Tree[root].Sum+=(e-s+1)*j;

        if( s>Tree[root].Mid() )
            Add( root*2+2, s, e, j );
        else
            if( e<=Tree[root].Mid() )
            Add( root*2+1, s, e, j );
        else
        {
            Add( root*2+1, s, Tree[root].Mid(), j );
            Add( root*2+2, Tree[root].Mid()+1, e, j );
        }
}

long long Query( int root, int s, int e )// 查询 区间[s,e]的和
{
        if( Tree[root].L==s && Tree[root].R==e )
                return Tree[root].Sum+Tree[root].Inc*(e-s+1);

        Tree[root].Sum+=(Tree[root].R-Tree[root].L+1)*Tree[root].Inc;
        Add( 2*root+1, Tree[root].L, Tree[root].Mid(), Tree[root].Inc );
        Add( 2*root+2, Tree[root].Mid()+1, Tree[root].R, Tree[root].Inc );
        Tree[root].Inc = 0;

        if( e<=Tree[root].Mid() )
                return Query( root*2+1, s, e );
        else
            if( s>Tree[root].Mid() )
                return Query( root*2+2, s, e );
        else
                return Query( root*2+1, s, Tree[root].Mid() ) +
                              Query( root*2+2, Tree[root].Mid()+1, e );
}

int main()
{
        int N, Q, a, b, c;
        char Cmd;
        scanf( "%d%d", &N, &Q );
        CreatTree( 0, 1, N );
        for( int i=1; i<=N; i++ )
        {
                scanf( "%d", &a );
                Insert( 0, i, a );
        }
        for( int i=0; i<Q; i++ )
        {
                cin>>Cmd;
                if( Cmd == 'Q' )
                {
                        scanf( "%d%d", &a, &b );
                        printf( "%I64d\n", Query( 0, a, b ) );
                }
                else
                {
                        scanf( "%d%d%d", &a, &b, &c );
                        Add( 0, a, b, c );
                }
        }
        return 0;
}

代码虽然长了点但都是线段树的基本操作，所以整体思路还是清晰的，还有一个版本是 节点带有左右子节点指针的，省空间那种，容易错比赛时候最好还是避免，平时当练习也不错，现在我就去用带指针的做一遍。