This documentation is automatically generated by competitive-verifier/competitive-verifier
区間取得・一点更新可能な要素数 $n$ のセグメント木.
segtree(n, func, e)
:要素数 n
のセグメント木を構築する.segtree(v, func, e)
:配列 v
の要素を持つセグメント木を構築する.func
は二項演算の関数,e
は単位元.$n \leq 10^8$ 程度.
update(idx, val)
:idx
番目の要素を val
に更新する.add(idx, val)
:idx
番目の要素を val
との二項演算の結果に更新する.get(idx)
:idx
番目の要素を返す.get(L, R)
:区間 [L, R)
の二項演算の結果を返す.get_all()
:全区間の二項演算の結果を返す.idx
, L
, R
は 0-indexed である.
二項演算の計算量を $O(1)$ と仮定したときの計算量を示す.
segtree(n, func, e)
:$O(n)$segtree(v, func, e)
:$O(n)$update(idx, val)
:$O(\log n)$add(idx, val)
:$O(\log n)$get(idx)
:$O(1)$get(L, R)
:$O(\log n)$get_all()
:$O(1)$#pragma once
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
template<typename T, typename F> struct segtree {
private:
int siz = 1, N;
vector<T> node;
const F op;
const T e_;
public:
segtree(int n, const F func, const T e) : N(n), op(func), e_(e) {
while(siz < N) siz <<= 1;
node.resize(2 * siz - 1, e_);
}
segtree(const vector<T> &v, const F func, const T e) : N(v.size()), op(func), e_(e) {
while(siz < N) siz <<= 1;
node.resize(2 * siz - 1, e_);
for(int i = 0; i < N; i++) node[siz - 1 + i] = v[i];
for(int i = siz - 2; i >= 0; i--) node[i] = op(node[2 * i + 1], node[2 * i + 2]);
}
void update(int idx, T val) {
idx += siz - 1;
node[idx] = val;
while(idx > 0) {
idx = (idx - 1) / 2;
node[idx] = op(node[2 * idx + 1], node[2 * idx + 2]);
}
}
void add(int idx, T val) {
idx += siz - 1;
node[idx] = op(node[idx], val);
while(idx > 0) {
idx = (idx - 1) / 2;
node[idx] = op(node[2 * idx + 1], node[2 * idx + 2]);
}
}
T get(int idx) {
assert(0 <= idx && idx < N);
return node[siz - 1 + idx];
}
T get(int L, int R) {
if(L < 0) L = 0;
if(R > N) R = N;
assert(L < R);
return get__(L, R, 0, 0, siz);
}
private:
T get__(int L, int R, int id, int l, int r) {
if(r <= L || R <= l) return e_;
if(L <= l && r <= R) return node[id];
T vl = get__(L, R, 2 * id + 1, l, (l + r) / 2);
T vr = get__(L, R, 2 * id + 2, (l + r) / 2, r);
return op(vl, vr);
}
public:
T get_all() {
return node[0];
}
};
#line 2 "tree/segtree.cpp"
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
template<typename T, typename F> struct segtree {
private:
int siz = 1, N;
vector<T> node;
const F op;
const T e_;
public:
segtree(int n, const F func, const T e) : N(n), op(func), e_(e) {
while(siz < N) siz <<= 1;
node.resize(2 * siz - 1, e_);
}
segtree(const vector<T> &v, const F func, const T e) : N(v.size()), op(func), e_(e) {
while(siz < N) siz <<= 1;
node.resize(2 * siz - 1, e_);
for(int i = 0; i < N; i++) node[siz - 1 + i] = v[i];
for(int i = siz - 2; i >= 0; i--) node[i] = op(node[2 * i + 1], node[2 * i + 2]);
}
void update(int idx, T val) {
idx += siz - 1;
node[idx] = val;
while(idx > 0) {
idx = (idx - 1) / 2;
node[idx] = op(node[2 * idx + 1], node[2 * idx + 2]);
}
}
void add(int idx, T val) {
idx += siz - 1;
node[idx] = op(node[idx], val);
while(idx > 0) {
idx = (idx - 1) / 2;
node[idx] = op(node[2 * idx + 1], node[2 * idx + 2]);
}
}
T get(int idx) {
assert(0 <= idx && idx < N);
return node[siz - 1 + idx];
}
T get(int L, int R) {
if(L < 0) L = 0;
if(R > N) R = N;
assert(L < R);
return get__(L, R, 0, 0, siz);
}
private:
T get__(int L, int R, int id, int l, int r) {
if(r <= L || R <= l) return e_;
if(L <= l && r <= R) return node[id];
T vl = get__(L, R, 2 * id + 1, l, (l + r) / 2);
T vr = get__(L, R, 2 * id + 2, (l + r) / 2, r);
return op(vl, vr);
}
public:
T get_all() {
return node[0];
}
};