アルゴリズムトレーニング-セグメントツリー

WIKIOI-1080線分樹練習
タイトルはDescriptionの1行のN個の四角格子を説明して、初めに各格子の中ですべて1つの整数があります.質問の形式はある特定のサブ区間[a,b]のすべての要素の和を求めることである.
変更されたルールは、ある格子xを指定し、特定の値Aを加算または減算することです.今、質問ごとに正しい答えを求めています.1≦N<100000,,質問と修正の総数
m<10000本.
入力記述Input Description入力ファイルの最初の動作は整数Nであり、次にn行n個の整数であり、格子内の元の整数を表す.次の正の整数mに続いて、次にm行があって、mの質問を表して、最初の整数
問合符号を表し、問合符号1は増加を表し、後の2つの数xとAは位置X上の数値増加Aを表し、問合符号2は区間和を表し、後の2つの整数はaとbを表し、
[a,b]間の区間和が要求される.
出力記述Output Description共m行、各整数
サンプル入力Sample Input 6 4 5 6 2 1 3 4 4 1 3 5 2 1 4 1 9 2 6サンプル出力Sample Output 22データ範囲およびヒントData Size&Hint 1≦N≦100000,m≦10000.
 
 
 
 
本題の目的は線分木の構造ACコードを訓練することである.

#include<stdio.h>
#include<string.h>
struct node//            
{
   int l,r;
   int sum;
}a[400010];//      2*N     ，       ！！
void Bulid(int n,int l,int r)//       [l,r]     
{
     a[n].l=l;//      
     a[n].r=r;//      
     a[n].sum=0;//      
     if(l==r)//        ,     
     return;
     Bulid(2*n,l,(l+r)/2);//      
     Bulid(2*n+1,(l+r)/2+1,r);//      
}
void Insert(int n,int v,int num)//         v   num 
{
     a[n].sum+=num;//     
     if(a[n].l==a[n].r)//       ，     
     return;
     if(v<=(a[n].l+a[n].r)/2)//       ，      ，       
     Insert(n*2,v,num);
     else
     Insert(n*2+1,v,num);
}
void Change(int n,int v,int num)//         v   （  num） 
{
     if(v==a[n].l&&v==a[n].r)//      ，     
     {
        a[n].sum+=num;
        return;
     }
     else
     if(v<=(a[n].l+a[n].r)/2)//       ，      ，      
     Change(n*2,v,num);
     else
     Change(n*2+1,v,num);
     a[n].sum=a[n*2].sum+a[n*2+1].sum;//              ，     
}
int Sum(int n,int l,int r)//       l、r        
{
     if(l==a[n].l&&r==a[n].r)//        ，          
     return a[n].sum;
     if(r<=(a[n].l+a[n].r)/2)//        ，         
     return Sum(n*2,l,r);
     else
     if(l>(a[n].l+a[n].r)/2)//        ，         
     return Sum(n*2+1,l,r);
     else//         ，i、r   a[n].l a[n].r  ，       
     return Sum(n*2,l,(a[n].l+a[n].r)/2)+Sum(n*2+1,(a[n].l+a[n].r)/2+1,r);
     
}
int main()
{
    int i,j,n,m,Q,L,R;
    scanf("%d",&n);
    Bulid(1,1,n);
    for(i=1;i<=n;i++)
    {
       scanf("%d",&m);
       Insert(1,i,m);
    }
    scanf("%d",&m);
    while(m--)
    {
       scanf("%d %d %d",&Q,&L,&R);
       if(Q==1) 
       {
          Change(1,L,R);
       } 
       else if(Q==2)
       {
          printf("%d
",Sum(1,L,R));
       }
    }
    return 0;
}

このコードはオリジナルで、転載は出典を明記してください!