JavaScriptでセグメントツリー

まえがき

前々から身につけたいと思っていたセグメントツリーを学習し
AtCoderでACすることができたのでここに記事として残す
応用範囲が広く解説するのも一苦労なので時間のある時に追記していきたい

目次

・ソースコード
・実際に使ってみた
・あとがき

ソースコード

class SegmentTree {
  constructor(n) {
    this.leafSize = 0
    this.data = []
    this.init(n)
  }

  init(n) {
    let leafSize = 1
    while (leafSize < n) {
      leafSize *= 2
    }
    this.leafSize = leafSize
    this.data = Array(2 * leafSize - 1).fill(Number.MAX_SAFE_INTEGER)
  }

  update(k, a) {
    k += this.leafSize - 1
    this.data[k] = a
    while (k > 0) {
      k = Math.floor((k - 1) / 2)
      this.data[k] = Math.min(this.data[k * 2 + 1], this.data[k * 2 + 2])
    }
  }

  get(k) {
    k += this.leafSize - 1
    return this.data[k]
  }

  query(a, b, k, l, r) {
    if (r < a || b < l) return Number.MAX_SAFE_INTEGER
    if (a <= l && r <= b) {
      return this.data[k]
    }
    let vl = this.query(a, b, k * 2 + 1, l, Math.floor((l + r) / 2))
    let vr = this.query(a, b, k * 2 + 2, Math.ceil((l + r) / 2), r)
    return Math.min(vl, vr)
  }

}

実際に使ってみた

E - Alternating String

使い所はすぐにわかる、クエリ問題で列の変更と列の区間を求める問題はセグメントツリーだ
愚直に解くとクエリの数かける列の全体を調査するので計算量はO(Q*N)となり間に合わない
この場合、最大で
5 * 10^5 * 5 * 10^5
≒ 10^11 でTLEとなる
提出結果 TLE 3319ms

だがセグメントツリーを使えば計算量はO(Q*logN)になるので間に合う
この場合、最大でも
5 * 10^5 * log(5 * 10^5)
= 5 * 10^5 * (log5 + 5log10)
≒ 5 * 10^5 * (2.3 + 5 * 3.3)
≒ 10^6
(２分木なのでlogの底は2、値は計算サイトから算出)
提出結果 AC 1751ms

セグメントツリー問題は一目でセグメントツリーを使うとわかるので
問題の本質はセグメントツリーの中にどんなデータを入れるかだ
本問の場合、隣り合う文字の関係を配列にし、文字を反転させても影響があるのは両端のみだと気づく必要がある
初見では分からなかったが次、同様の問題が出た場合は解けるよう精進していきたい

あとがき

セグメントツリーを身につけたかった
なぜならAtcoderで頻出のデータ構造だからだ
Atcoderの参加回数とレーティングの統計によると
私ぐらいの参加回数だと緑レベルが平均的なようだが
残念ながら私は未だ茶色コーダーだ
私はjsをメインに使っているので
「ライブラリが充実していないので仕方がない」
「C++を使ってたなら今頃もっと上のレートだった、まだ本気を出してないだけ」
という言い訳を作ることもできるが
実力の伴わない現実から目を逸らし自己を向上させることから逃げたくはない
学ぼうと思ってから実際に行動に移すまで想定よりも時間はかかったが
なんとか競プロ中級の入口レベルには到達したように思う

素直にC++使えよって意見についてはもっともだとは思うが
私は他の人がやっていないことをやるのが好きなのだ
レーティングが完全に頭打ちになるまではjsを使い続けようと思う
次に学習したいこととしてよく目にするけど未だ理解していない巡回セールスマン問題あたりを解けるように頑張りたい