atcoder136で丁寧にSegment TreeとBIT(Binary Indexed Tree)を解説してくれています

解説動画(2:11:~~)くらいから必要な前提知識としてBITを説明されています。

以下は、その解説の発端となったatcoder136のF問題です。

BITは、配列のこれまでの総和をうまく計算するためのデータ構造の一つです。

他にも、Segment Treeというもんがあります。どちらも総和をBinary Tree構造で持ちます。

Segment TreeもBinary Treeも概ね一緒で、O(logN)で区間の総和を求めることができますが、

Binary Treeのほうが、Segment Treeより実装が楽で、ちょっとだけ速いです。

indexed問われる所以は左から、二進表示したときに

二進法の最初の1が現れるまでの数と、区間数が一致する、性質をうまく利用しています。

iの最後のビットは`i & -i`で表せることを利用しているからだと思います。

蟻本でも解説されており、その中での実装方法はこのようになっています。

i-=i& -iは`i = i & (i-1)`とも書けます

bit = [0] * (MAX_N + 1)

def sum(i: int):
  s = 0
  while i > 0:
    s += bit[i]
    i -= i & -i
  return s

def add(i: int, x: int):
  while i <= n:
    bit[i] += x
    i -= i & -i

出典：プログラミングコンテストチャレンジブック第２版

ちなみに、それを使う問題の１例は、bubble sortの回数を答える問題です。

普通に数えるとO(N^2)かかってしまいますが、BITを使えばO(NlogN)ですね。

最後に、BITで総和がすでに昇順に並んでいるので、bisectとかで二分検索ができます。

あと平面走査(Line Sweep)も、よくつかわれる技だと、言うので覚えておきましょう。

以上が問題fのポイントです。

atcoder136のe問題は同じ動画のこのへんがE問題の解説ですが、ポイントは

・約数の見つけ方(基本）と

// Xの約数はXの平方根(ルートX)以上同士の掛け算にはならない、ということもサラッと大事
for(int i = 1; i * i <= sum; i++) {
  if (sum % == 0) {
    iは約数 
    sum//iも約数
  }
}

・全部をXの倍数にするために必要な操作回数は？という問題への変換　の流れを解説で聞くことができる

問題です。解説者もおっしゃっていましたが、難しい問題です。

以上です。