7K4B blog

猫でも分かる何か

ABC157 E - Simple String Queries

f:id:tkr987:20200617102759p:plain

https://atcoder.jp/contests/abc157/submissions/13434967

  • BITで点加算と範囲取得が O(\log N)
  • BITを複数本もつデータ構造に慣れる

f:id:tkr987:20200617104320p:plain

文字列の長さが 10^5でクエリ数が 10^4あることから、合計を求めるクエリ1個につき O(1)または O(\log N)で処理したいという気持ちになる。そこで、Binary Indexed Treeを使う。BIT1個だと実現できないが、アルファベットaからzまで全部で26個のBITを用意すれば実現できることに気づけば簡単。BITを使ってクエリ毎に任意範囲の各文字の合計を取得したり、クエリ毎に任意要素の各文字の個数を変更（1か0）すれば、計算量は Q \log Nになる。