Range Query on a Tree ～木上の1点加算、根までの和～

• Quiz
  • http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_D&lang=ja
• AC
  • http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4879659#1
• 解説
  • 辺に足すという操作は、葉側の頂点に足すと言い換えてOK
  • get sumクエリが来たときは、指定された頂点から根までの和を求める
  • この2つの操作をO(logN)で行いたい
  • オイラーツアー＆BITを使う
  • 下記のコードのように行えばいい

EulerTour tour(N);
BIT bit(2*N);
ll Q;cin>>Q;
while(Q--){
  ll ty;cin>>ty;
  if(ty==0){
    // add
    ll v,w;cin>>v>>w;
    bit.add(tour.L[v], w);
    bit.add(tour.R[v]+1, -w);
  }
  else{
    // get sum
    ll u;cin>>u;
    ll ans = bit.sum(tour.L[u]);
    p(ans);
  }
}