C - 積み木 (arc031_3)

Quiz

https://atcoder.jp/contests/arc031/tasks/arc031_3

Submit

https://atcoder.jp/contests/arc031/submissions/4187330

解法

• editorial参照
• 上記メモはSegment木だが、実際は実装が楽に済むBinary Indexed Tree (BIT) で解く

感想

• BITはSegment木より対称性がないので難しい印象があったが、書いてみるとSegment木よりも楽だった
  • 「値の更新」「和を求める」共にwhileの終了条件が明らかで書きやすい

参考

• https://www.slideshare.net/hcpc_hokudai/binary-indexed-tree
  • BIT
  • 値の更新
  • 和を求める

学び

• BIT
• LSB (Least Significant Bit) a & -a