Segtree

モノイド $(S, \cdot: S \times S \to S, e \in S)$、つまり

結合律: $(a \cdot b) \cdot c$ = $a \cdot (b \cdot c)$ for all $a, b, c \in S$
単位元の存在: $a \cdot e$ = $e \cdot a$ = $a$ for all $a \in S$

を満たす代数構造に対し使用できるデータ構造です。

長さ $N$ の $S$ の配列に対し、

要素の $1$ 点変更
区間の要素の総積の取得

を $O(\log N)$ で行うことが出来ます。詳細な要件は Appendix を参照してください。

また、このライブラリはオラクルとしてop, eの2種類を使用しますが、これらが定数時間で動くものと仮定したときの計算量を記述します。オラクル内部の計算量が $O(f(n))$ である場合はすべての計算量が $O(f(n))$ 倍となります。

コンストラクタ

(1) var seg = initSegTree[S](n:int, op:(S,S)->S, e:()->S):segtree[S]
    var seg = SegTreeType(S, op:(S,S)->S, e:()->S).init(n)
    var seg = SegTree.getType(S, op:(S,S)->S, e:()->S).init(n)
(2) var seg = initSegTree[S](v:seq[S], op:(S,S)->S, e:()->S):segtree[S]
    var seg = SegTreeType(S, op:(S,S)->S, e:()->S).init(v)
    var seg = SegTree.getType(S, op:(S,S)->S, e:()->S).init(v)

型 S
二項演算 op(a:S, b:S):S
単位元 e():S

を定義する必要があります。例として、Range Min Queryならば

proc op(a:int, b:int):int =
    return min(a, b)

proc e():int =
    return 10^9

var seg = initSegTree[int](10, seg, e)

のようになります。

(1): 長さ n の数列 a を作ります。初期値は全部e()です。
(2): 長さ n = v.len の数列 a を作ります。v の内容が初期値となります。

詳しくは、使用例やこちらも参照してください。

制約

$0 \leq n \leq 10^8$

計算量

$O(n)$

タイプだけ設定

  type st_type = SegTreeType[S](op:(S,S)->S, e:()->S)

コンストラクタは呼ばずにタイプだけ設定できます。st_type.init(v:seq[int])といった具合にタイプからコンストラクタを呼び出したり、var v:seq[st_type]といった具合にsegtreeの配列を宣言するのにお使いください。

(背景)Nimはいろいろと癖のある言語でsegtreeのobject構造体はマニアック(笑)な構造をしているので直にタイプを呼ぶのは推奨されません。上記のSegTreeTypeのテンプレートをお使いください。

set

seg.set(p:int, x:S):void
seg[p:int] = x:S

a[p] に x を代入します。

制約

$0 \leq p < n$

計算量

$O(\log n)$

get

seg.get(p:int):S
seg[p:int]:S

a[p] を返します。

制約

$0 \leq p < n$

計算量

$O(1)$

prod

seg.prod(l..<r):S
seg[l..<r]:S

op(a[l], ..., a[r - 1]) を、モノイドの性質を満たしていると仮定して計算します。$l = r$ のときは e() を返します。

制約

$0 \leq l \leq r \leq n$

計算量

$O(\log n)$

all_prod

seg.all_prod():S

op(a[0], ..., a[n - 1]) を計算します。$n = 0$ のときは e() を返します。

計算量

$O(1)$

max_right

(1) seg.max_right<f>(l:int):int
(2💻) seg.max_right[F](l:int, f:F):int

(1): 関数 bool f(S x) を定義する必要があります。segtreeの上で二分探索をします。
(2): Sを引数にとりboolを返す関数オブジェクトを渡して使用します。

以下の条件を両方満たす r を(いずれか一つ)返します。

r = l もしくは f(op(a[l], a[l + 1], ..., a[r - 1])) = true
r = n もしくは f(op(a[l], a[l + 1], ..., a[r])) = false

fが単調だとすれば、f(op(a[l], a[l + 1], ..., a[r - 1])) = true となる最大の r、と解釈することが可能です。

制約

fを同じ引数で呼んだ時、返り値は等しい(=副作用はない)
f(e()) = true
$0 \leq l \leq n$

計算量

$O(\log n)$

min_left

(1) seg.min_left[f](r:int):int
(2💻) seg.min_left[F](r:int, f:F):int

(1): 関数 bool f(S x) を定義する必要があります。segtreeの上で二分探索をします。
(2): Sを引数にとりboolを返す関数オブジェクトを渡して使用します。

以下の条件を両方満たす l を(いずれか一つ)返します。

l = r もしくは f(op(a[l], a[l + 1], ..., a[r - 1])) = true
l = 0 もしくは f(op(a[l - 1], a[l], ..., a[r - 1])) = false

fが単調だとすれば、f(op(a[l], a[l + 1], ..., a[r - 1])) = true となる最小の l、と解釈することが可能です。

制約

fを同じ引数で呼んだ時、返り値は等しい(=副作用はない)
f(e()) = true
$0 \leq r \leq n$

計算量

$O(\log n)$

使用例

AC code of https://atcoder.jp/contests/practice2/tasks/practice2_j

import atcoder/header import atcoder/segtree import sequtils, sugar let n, q = nextInt() let a = newSeqWith(n, nextInt()) var target:int proc f(v:int):bool = v < target var seg = initSegTree[int](a, (a:int,b:int)=>max(a, b), () => -1) for i in 0..<q: let t = nextInt() if t == 1: var x, v = nextInt() x.dec seg.set(x, v); elif t == 2: var l, r = nextInt() l.dec echo seg.prod(l..<r) elif t == 3: let p = nextInt() - 1 target = nextInt() echo seg.max_right(p, f) + 1

Monoid記述子による構築

atcoder/extra/structure/monoid_segtreeをimportすると、 Monoid記述子から構築できます。

var tree = SumMonoid.initSegTree(values)
var emptyTree = SumMonoid.initSegTree(n)

長さconstructorは各葉をMonoidの単位元で初期化します。既存のcallback constructorも維持されます。