UESTC 1073秋実長兄と線分樹線分樹&&改値と区間とor樹状配列

秋実兄貴と線分樹
Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
Submit  Status
秋実さんは携帯電話をいじっている後輩に言った.
秋実さんは勉強が好きな人で、今日は線分樹というデータ構造を勉強したばかりです.
自分の掌握度を検証するために、秋実兄貴は自分に1つの問題を出して、同時にみんなを誘って一緒に作りました.
秋実兄貴のテーマはあなたに1つのシーケンスを維持することを要求して、2つの操作をサポートします:1つはある要素の値を修正することです;一つは区間の和を尋ねることです.
Input
最初の行には、シーケンスの長さを表す整数nが含まれます.
次の行には、シーケンスの初期を表すn個の整数aiが含まれます.
次の行には、オペランドを表す整数mが含まれます.
次にm m行、各行は以下の2つの操作の1つです.

1 x v :     x       v
2 l r :     [l,r]        

1≤n,m,v,ai≤100000  1≤l≤r≤n      
Output
各2について  l    r   操作して、1つの整数が1行を占めて、対応する答えを表します.
Sample input and output
Sample Input
Sample Output

3
1 2 3
3
2 1 2
1 1 5
2 1 2

3
7

Source
2015 UESTC Training for Data Structures
The question is from
 
here.
My Solution
注意データオーバーフロー n<=1 e 5,ai<=1 e 5の場合sum[i]<=1 e 10;100億とかintで明らかに溢れてる
1、木を作るときはModify、つまり直接値を変える関数を使う

#include <iostream>
#include <cstdio>
#include <cstring>
typedef long long LL;
using namespace std;
const int maxn = 1<<(20);

LL sum[maxn];
int size;
LL _Query(int a,int b,int l,int r,int Ind){
    if(a <= l && b >= r) return sum[Ind];
    int mid = (l+r)>>1; LL ret = 0;
    if(a <= mid) ret = ret + _Query(a,b,l,mid,Ind<<1);
    if(b > mid) ret = ret + _Query(a,b,mid+1,r,(Ind<<1)+1);
    return ret;
}

void _Modify(int a,int l,int r,int Ind,int d){
    if(l == r && l == a){
        sum[Ind] = d;
        return;
    }
    int mid = (l+r)>>1;
    if(a <= mid) _Modify(a,l,mid,Ind<<1,d);
    else _Modify(a,mid+1,r,(Ind<<1)+1,d);
    sum[Ind] = sum[Ind<<1] + sum[(Ind<<1)+1];
}

LL Query(int a,int b) {return _Query(a,b,1,size,1);}
void Modify(int a,int d){return _Modify(a,1,size,1,d);}

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    #endif // LOCAL

    int  n,v;
    scanf("%d", &n); size = n;
    for(int i = 1; i <= size; i++){
        scanf("%d", &v);
        Modify(i,v);
    }
    int m, x, y, z;
    scanf("%d", &m);
    while(m--){
        scanf("%d%d%d", &x, &y, &z);
        if(x == 1) Modify(y,z);
        else printf("%lld
", Query(y,z));
    }
    return 0;
}

2、木を建てる时に改版のModifyで入れて、最后の时、また各ノードの情报を返して维持します;

#include <iostream>
#include <cstdio>
#include <cstring>
typedef long long LL;
using namespace std;
const int maxn = 1<<(20);

LL sum[maxn];
int size;
LL _Query(int a,int b,int l,int r,int Ind){
    if(a <= l && b >= r) return sum[Ind];
    int mid = (l+r)>>1; LL ret = 0;
    if(a <= mid) ret = ret + _Query(a,b,l,mid,Ind<<1);
    if(b > mid) ret = ret + _Query(a,b,mid+1,r,(Ind<<1)+1);
    return ret;
}

void _Modify(int a,int l,int r,int Ind,int d){
    if(l == r && l == a){
        sum[Ind] = d;
        return;
    }
    int mid = (l+r)>>1;
    if(a <= mid) _Modify(a,l,mid,Ind<<1,d);
    else _Modify(a,mid+1,r,(Ind<<1)+1,d);
    sum[Ind] = sum[Ind<<1] + sum[(Ind<<1)+1];
}

void _Build(int a,int l,int r,int Ind,int d){
    if(l == r && l == a){
        sum[Ind] = d;
        return;
    }
    int mid = (l+r)>>1;
    if(a <= mid) _Modify(a,l,mid,Ind<<1,d);
    else _Modify(a,mid+1,r,(Ind<<1)+1,d);
    //sum[Ind] = sum[Ind<<1] + sum[(Ind<<1)+1];
}

LL Query(int a,int b) {return _Query(a,b,1,size,1);}
void Modify(int a,int d){return _Modify(a,1,size,1,d);}
void Build(int a,int d){return _Build(a,1,size,1,d);}

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    #endif // LOCAL

    int  v;
    scanf("%d", &size);
    for(int i = 1; i <= size; i++){
        scanf("%d", &v);
        if(i!=size) Build(i,v);
        else Modify(i,v);
    }
    int m, x, y, z;
    scanf("%d", &m);
    while(m--){
        scanf("%d%d%d", &x, &y, &z);
        if(x == 1) Modify(y,z);
        else printf("%lld
", Query(y,z));
    }
    return 0;
}

3、木を建てるときはきっともっと早くできるよ、へへへ☺☺でもできない
4、木の形の配列、テーマはわざとで、このテーマの最も適当な方法は木の形の配列を使うべきです☺
Thank you!