Nim-ACL

Range utilities

概要

rangeutilsはNimのSlice、HSlice、BackwardsIndexを、 データ構造内部で扱いやすい半開区間[l, r)へ変換します。

Fenwick Tree、Segment Tree、Lazy Segment Tree、Sparse Table、 Rolling Hashなどで共通利用されています。

import

import atcoder/rangeutils

対応するrange表記

type RangeType =
  Slice[int] |
  HSlice[int, BackwardsIndex] |
  HSlice[BackwardsIndex, int] |
  Slice[BackwardsIndex]

長さ8のcontainerでは、次のように正規化されます。

表記 意味 [l, r)
2 .. 4 両端を含む [2, 5)
2 ..< 5 右端を含まない [2, 5)
2 .. ^1 index 2から末尾まで [2, 8)
^3 .. ^1 末尾相対index同士 [5, 8)
^3 .. 6 末尾相対の左端 [5, 7)
^3 ..< 7 末尾相対の左端・半開 [5, 7)
^3 ..< 5 空区間 [5, 5)
0 ..< ^0 全区間 [0, 8)
^0 ..< ^0 末尾の空区間 [8, 8)
0 .. ^0 clampしないclosed range [0, 9)

^kはcontainer.len - kへ変換されます。 したがって^1は最後の要素、^0は末尾の直後を表します。

全区間には0 ..< ^0を使用してください。 0 .. ^0はclosed右端をさらに1増やすため、 通常のデータ構造に対しては範囲外になります。

公開API

type RangeType
type IndexType

template halfOpenEndpoints(
    p: Slice[int]
): (int, int)

template halfOpenEndpoints(
    container,
    p: RangeType
): (int, int)

整数endpointだけのrangeはcontainerなしでも変換できます。

doAssert halfOpenEndpoints(2 .. 4) == (2, 5)
doAssert halfOpenEndpoints(2 ..< 2) == (2, 2)

BackwardsIndexを含むrangeでは、 長さを得るためcontainerを指定します。

let values = @[10, 20, 30, 40, 50]

doAssert values.halfOpenEndpoints(1 .. ^1) == (1, 5)
doAssert values.halfOpenEndpoints(^3 .. 3) == (2, 4)
doAssert values.halfOpenEndpoints(0 ..< ^0) == (0, 5)

データ構造での使用例

import atcoder/fenwicktreeimport atcoder/rangeutilsvar tree = initFenwickTree[int](8)for i in 0 ..< 8:  tree.add(i, i + 1)doAssert tree.sum(2 .. 4) == 12doAssert tree.sum(2 ..< 5) == 12doAssert tree.sum(2 .. ^1) == 33doAssert tree.sum(^3 ..< 7) == 13doAssert tree.sum(0 ..< ^0) == 36

既存のsum(l, r)やprod(l, r)などの(l, r)形式も 引き続き利用できます。

境界条件

計算量

操作 計算量
整数endpointの正規化 O(1)
BackwardsIndexの正規化 O(1)
追加領域 O(1)

関連

検証

専用testで以下を確認しています。