そのうち誰かの役に立つ

もしくは誰の役にも立たない

セグメント木(Segment Tree)

アルゴリズムとデータ構造 Segment Tree Python3 Go

概要

  • 要素の更新がありうる数列について、任意区間におけるあらかじめ定義した演算が高速にできる
    • 最大値/最小値
    • 一定値以上/以下の要素数
    • 区間和
  • 数列の各要素が葉となるような木構造をとる
  • 木を構成する各nodeは自身の子node（葉の場合は自分自身）が表現している区間全体についての演算結果を持つ
  • 葉の値（数列の要素）を変更した場合、そこから根に向かって各nodeの演算結果を更新していく
  • 数列 A = [a_0, a_1, \dots , a_{n - 1}] について、ある区間 [a_l, \dots , a_r] (0 \leq l \leq r \leq n - 1) の演算結果を取得したい場合は下記の計算を根から実行する
    • そのnodeが表現する区間 [a_x, \dots , a_y] が求めたい区間に内包される (l \leq x かつ y \leq r) 場合、nodeの持つ演算結果を返す
    • そのnodeが表現する区間 [a_x, \dots , a_y] が求めたい区間と互いに素である (y \lt l または r \lt x) 場合、最大値/最小値なら十分小さな/大きな数、要素数や区間和なら0を返す
    • どちらでもない場合は子nodeに演算を渡し、返ってきた結果から計算された値を返す
  • 計算時間は要素の更新に O(\mathrm{log}n) 、演算結果の取得に O(\mathrm{log}n)

実装

  • 簡単のため数列の各要素は整数とする
  • 演算は任意に事前定義可能とする
    • 今回は区間内の最小値とする
  • 数列の i 番目の要素を v に更新する関数 Update(i, v) をもつ
  • 任意の区間 [a_l, \dots , a_r] における演算結果を返す関数 Get(l, r) をもつ

Python3で実装する

Powered by OnlineGDB

Goで実装する

Goでデフォルト引数を使うのは何かとめんどくさいので GetVal(l, r, i) 関数を定義し、 Get(l, r) 関数は GetVal(l, r, 1) を呼び出すWrapperとした