P163 A Simple Probrem with Integers

区間への加算と和の計算がO(log(n))できるセグメント木が良く分からなかったので、図に書いてみた。
（普通のセグメント木はある要素への加算と和の計算がO(log(n))である。）

上の図では、まずそれぞれの要素に{3,6,1,2,5,8,1,4}を加えた後、[1,6)に2を加算している。
また各節点の数字は、１つ目がdata、２つ目がdatbに対応している。

1つ目の木について

葉では全て一様に加えられているので、dataにその加えられた値が格納される。
葉以外の節点では全て一様でなく加えられているので、datbにその和が格納される。

2つ目の木について

節点[1,2),[2,4), [4,6)では一様に加えられているので、dataに2が加算される。
それらの節点の子には何もしない。
それらの親にあたる節点ではdatbが更新されている。

和の計算

求めたい区間をIとする。
再帰的に計算するわけだが、今の節点がIに含まれていれば、
data * その区間の大きさ + datb
が返り値となり、今の節点がIに含まれていなければ（部分的に含まれていれば）、
data * その区間とIの共通部分の大きさ + ２つの子の和
となる。
例としてI=[3,6)の和を計算する事を考える。
式は、
2*1+2 + 2*2 + 13 = 21
となり、正しく求められている事が分かる。

やっとBITへの応用が読める・・・。