point set range min

C++ 用ライブラリ一覧に戻る

ソースコード

nachia/range-query/point-set-range-min.hpp

主な機能

配列 $(a[0],a[1],\ldots ,a[n])$ に対して、次の計算を高速化する。

• $p,x$ : $a[p]$ の値を $x$ で上書きする。
• $l,r$ : $\min _ {i=l} ^ {r-1} a[i]$ を計算する。

構造体テンプレート PointSetRangeMin

テンプレート引数

template<class S, class Cmp = std::less<S>>
struct PointSetRangeMin;

要素の型 S と、集約の演算 Cmp を与える。

• Cmp のインスタンスをデフォルトコンストラクタで構築すると、比較演算 < として呼び出せる。

以降、 S の要素のコピーおよび Cmp の計算はそれぞれ $O(1)$ 時間で行えるとする。

コンストラクタ

PointSetRangeMin();    // (0)
PointSetRangeMin(int len, S INF);    // (1)
PointSetRangeMin(const std::vector<S>& init, S INF);   // (2)

• 要素数 $n$ : $0 \leq n \leq 10^8$
• 以降、 INF よりも大きい要素を考慮しない。

以下では INF を $\infty$ と表記する。

–

• (0) : ダミーを構築する。このインスタンスでは操作をしてはいけない。
• (1) : $n$ 要素を INF で初期化する。
• (2) : 配列 init で初期化する。

set

void set(int p, S x);

• $0 \leq p \lt n$
• $O( \log n )$ 時間

単一の要素への操作。 a[p] = x に相当する。

get

S get(int p) const;

• $0 \leq p \lt n$
• $O( 1 )$ 時間

a[p] を取得する。

min

S min(int l, int r) const; // (1)
S min() const;             // (2)

• $0 \leq l \leq r \leq n$
• $O( \log n )$ 時間

(1) : $\min\lbrace \infty,a[l],a[l+1],\ldots ,a[r-1]\rbrace$ の値を返す。

(2) : $\min\lbrace \infty,a[0],a[1],\ldots ,a[n-1]\rbrace$ の値を返す。

lBoundLeft, uBoundLeft, lBoundRight, uBoundRight

int lBoundLeft(int from, S val);  // (1)
int uBoundLeft(int from, S val);  // (2)
int lBoundRight(int from, S val); // (3)
int uBoundRight(int from, S val); // (4)

• $0 \leq \text{from} \leq n$
• $O( \log n )$ 時間

(1) : 以下の条件をすべて満たすような整数 $l$ を一つ求める。

• val < min(l,from)
• l == 0 || a[l-1] <= val

(2) : 以下の条件をすべて満たすような整数 $l$ を一つ求める。

• val <= min(l,from)
• l == 0 || a[l-1] < val

(3) : 以下の条件をすべて満たすような整数 $r$ を一つ求める。

• val < min(from,r)
• r == n || a[l-1] <= val

(4) : 以下の条件をすべて満たすような整数 $r$ を一つ求める。

• val <= min(from,r)
• r == n || a[r+1] < val

---

TOP PAGE