FenwickTree の中身

ary[i] = sum A[i - lowbit(i), i)

最下位の1を足す・引く

todo:なぜこううまくいくのか、裏の構造が有れば理解したい

13=8+4+1と分解する。doubling 経由LCAでも出てくるテク

区間の長さ

• 一番下は長さ1
• 下から2番めは長さ2
• 下から３番めは長さ4…

Fenwick Tree 現れる bit 演算テク

• x&(-x): 最下位の1のみ立ってる値

  最下位の1以下のbit (最下位の1より上の bit は省略)
  x     : 10000
  !x    : 01111
  -x    : 10000  (-x = !x + 1)
  x&(-x): 10000
  
  最下位の1以上のbit (最下位の1より下の bit は省略)
  x     : 10111
  !x    : 01001
  -x    : 01001 (+1の影響がない)
  x&(-x): 00001
  

• x&(x-1): 最下位の1 を 0 にした値

  最下位の1以下のbit (最下位の1より上の bit は省略)
  x      : 10000
  x-1    : 01111 (すべて反転)
  x&(x-1): 00000
  
  最下位の1以上のbit (最下位の1より下の bit は省略)
  x      : 10111
  x-1    : 10110 (最下位の1のみ反転)
  x&(x-1): 10110
  
  x-1 は x の最下位の1以下をすべて反転させるので、x&(x-1) で xの最下位以下をすべて0にして、
  それ以外は変化しないとなる。