线段树之单点更新求和hdoj1166

题目：hdoj1166

分析：题意很清晰，就是让你给某个点又增加或者减少x个，然后求某一段有多少个，我是用一个father数组保存叶子节点的编号，然后直接从当前节点开始，更轻到root就ok。

查询的话，从根节点开始，看在左子区间还是右子区间，直接查询到某一段全部在要查询的区间内，求和就ok，很简单。

代码：

#include 
  
   
#include 
   
     #include 
     
     using namespace std
     ; const int N
      = 55000
     ; struct Node
      { int l
     ,r
     ; int sum
     ; }; Node tree
     [4
     *N
     ]; int a
     [N
     ]; int fa
     [N
     ]; void build
     (int l
     ,int r
     ,int v
     ) { tree
     [v
     ].l
     =l
     ; tree
     [v
     ].r
     =r
     ; if(l
     ==r
     ) { fa
     [l
     ]=v
     ; tree
     [v
     ].sum
     =a
     [l
     ]; return ; } int mid
     =(l
     +r
     )>>1
     ; build
     (l
     ,mid
     ,v
     *2
     ); build
     (mid
     +1
     ,r
     ,v
     *2
     +1
     ); tree
     [v
     ].sum
     =tree
     [v
     +v
     ].sum
     +tree
     [v
     +v
     +1
     ].sum
     ; } void update
     (int t
     ,int p
     ) { tree
     [t
     ].sum
     +=p
     ; if(t
     ==1
     ) return ; update
     (t
     /2
     ,p
     ); } int queue
     (int a
     ,int b
     ,int v
     ) { if(tree
     [v
     ].l
     ==a
     &&tree
     [v
     ].r
     ==b
     ) { return tree
     [v
     ].sum
     ; } int mid
     =(tree
     [v
     ].l
     +tree
     [v
     ].r
     )>>1
     ; if(b
     <=mid
     ) return queue
     (a
     ,b
     ,v
     +v
     ); else if(a
     >mid
     ) return queue
     (a
     ,b
     ,v
     +v
     +1
     ); else return queue
     (a
     ,mid
     ,v
     *2
     )+queue
     (mid
     +1
     ,b
     ,v
     *2
     +1
     ); } int main() { int T
     ,n
     ; char str
     [10
     ]; int x
     ,y
     ; scanf
     ("%d"
     ,&T
     ); for(int cas
     =1
     ; cas
     <=T
     ; cas
     ++) { scanf
     ("%d"
     ,&n
     ); for(int i
     =1
     ; i
     <=n
     ; i
     ++) scanf
     ("%d"
     ,&a
     [i
     ]); build
     (1
     ,N
     ,1
     ); printf
     ("Case %d:\n"
     ,cas
     ); while(scanf
     ("%s"
     ,str
     )>0
     ) { if(str
     [0
     ]=='A'
     ) { scanf
     ("%d %d"
     ,&x
     ,&y
     ); update
     (fa
     [x
     ],y
     ); } else if(str
     [0
     ]=='S'
     ) { scanf
     ("%d %d"
     ,&x
     ,&y
     ); update
     (fa
     [x
     ],-y
     ); } else if(str
     [0
     ]=='Q'
     ) { scanf
     ("%d %d"
     ,&x
     ,&y
     ); int ans
     =queue
     (x
     ,y
     ,1
     ); printf
     ("%d\n"
     ,ans
     ); } else { break; } } } }