PrefixSum
クラス · 累積和
template <class T = std::int64_t, bool RangeAdd = false>
struct PrefixSum;
概要
累積和
テンプレートパラメータ
| 名前 | 説明 |
|---|---|
RangeAdd |
true なら区間加算（差分配列）、false なら点更新として構築する。 |
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
(1) 空の累積和を構築する (2) 長さnの0列を構築する (3) 列から累積和を構築する |
(1) $O(1)$ (2) $O(n)$ (3) $O(n)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
build |
build前の値から累積和を構築する | $O(n)$ |
get |
k番目の値を返す | $O(1)$ |
set |
v[k] = x（build 前のみ有効） | $O(1)$ |
add |
(1) v[k] += x（build 前のみ有効） (2) v[l … r-1] += x（build 前のみ有効） |
$O(1)$ |
sum |
(1) 接頭辞 $[0,r)$ の総和を返す (2) 半開区間 $[l,r)$ の総和を返す |
$O(1)$ |
lower_bound |
(1) 接頭辞和がx以上となる最初の位置を返す (2) lからの区間和がx以上となる最初の位置を返す |
$O(\log n)$ |
upper_bound |
(1) 接頭辞和がxより大きくなる最初の位置を返す (2) lからの区間和がxより大きくなる最初の位置を返す |
$O(\log n)$ |
メンバの詳細
(constructor)
// (1)
PrefixSum();
// (2)
PrefixSum(int _n);
// (3)
template <class U>
PrefixSum(const std::vector<U> &v);
(1) 空の累積和を構築する
- 計算量: $O(1)$
(2) 長さnの0列を構築する
- 計算量: $O(n)$
(3) 列から累積和を構築する
- 計算量: $O(n)$
add
// (1)
void add(int k, T x);
// (2)
void add(int l, int r, T x) requires RangeAdd;
(1) v[k] += x（build 前のみ有効）
- 計算量: $O(1)$
(2) v[l … r-1] += x（build 前のみ有効）
- 計算量: $O(1)$
sum
// (1)
T sum(int r) const;
// (2)
T sum(int l, int r) const;
(1) 接頭辞 $[0,r)$ の総和を返す
- 計算量: $O(1)$
(2) 半開区間 $[l,r)$ の総和を返す
- 計算量: $O(1)$
lower_bound
// (1)
int lower_bound(T x) const;
// (2)
int lower_bound(int l, T x) const;
(1) 接頭辞和がx以上となる最初の位置を返す
- 計算量: $O(\log n)$
(2) lからの区間和がx以上となる最初の位置を返す
- 計算量: $O(\log n)$
upper_bound
// (1)
int upper_bound(T x) const;
// (2)
int upper_bound(int l, T x) const;
(1) 接頭辞和がxより大きくなる最初の位置を返す
- 計算量: $O(\log n)$
(2) lからの区間和がxより大きくなる最初の位置を返す
- 計算量: $O(\log n)$