This documentation is automatically generated by competitive-verifier/competitive-verifier
区間取得・区間更新可能な要素数 $n$ のセグメント木. 各要素について更新時の作用素を保持しておき,値が必要になるタイミングで要素と作用素をマージする.
segtree_lazy(n, op, f_upd, f_lz, ex, em)
:要素数 n
のセグメント木を構築する.segtree_lazy(v, op, f_upd, f_lz, ex, em)
:配列 v
の要素を持つセグメント木を構築する.op(l, r)
は要素の二項演算,f_upd(x, m)
は要素と作用素をマージする二項演算,f_lz(l, r)
は作用素を蓄積するときの二項演算(マージ順は l
$\to$ r
).
ex
は要素の単位元,em
は作用素の単位元.
$n \leq 10^8$ 程度.
update(idx, val)
:idx
番目の要素を val
との二項演算 f_upd
の結果に更新する.update(L, R, val)
:[L, R)
番目の要素を val
との二項演算 f_upd
の結果に更新する.get(idx)
:idx
番目の要素を返す.get(L, R)
:区間 [L, R)
の二項演算 op
の結果を返す.idx
, L
, R
は 0-indexed である.
各二項演算の計算量を $O(1)$ と仮定したときの計算量を示す.
update(idx, val)
:$O(\log n)$update(L, R, val)
:$O(\log n)$get(idx)
:$O(\log n)$get(L, R)
:$O(\log n)$ある行列Aに行列Bを掛ける操作をすることは,Bを左から掛けることに相当する.
using mat = matrix<T>;
auto op = /* 任意の範囲取得クエリ */;
mat ex = /* opの単位元 */;
/* ある行列Aに行列Bを掛ける操作をすることは、Bを左から掛けることに相当する */
auto f_upd = [](mat A, mat B) { return B * A; };
mat em = mat::Indentity();
auto seg = segtree_lazy(v /* or N */, op, f_upd, f_upd, ex, em);
#pragma once
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
template<typename T, typename M> struct segtree_lazy {
using F = function<T(T, T)>;
using FU = function<T(T, M)>;
using FM = function<M(M, M)>;
private:
int siz = 1, N;
vector<T> node;
vector<M> lazy;
const F op;
const FU f_upd;
const FM f_lz;
const T ex;
const M em;
public:
segtree_lazy(int n, const F op, const FU f_upd, const FM f_lz, const T ex, const M em) :
N(n), op(op), f_upd(f_upd), f_lz(f_lz), ex(ex), em(em) {
while(siz < N) siz <<= 1;
node.resize(2 * siz - 1, ex);
lazy.resize(2 * siz - 1, em);
}
segtree_lazy(vector<T> &v, const F op, const FU f_upd, const FM f_lz, const T ex, const M em) :
N(v.size()), op(op), f_upd(f_upd), f_lz(f_lz), ex(ex), em(em) {
while(siz < N) siz <<= 1;
node.resize(2 * siz - 1, ex);
lazy.resize(2 * siz - 1, em);
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, M val) {
assert(0 <= idx && idx < N);
upd__(idx, idx + 1, 0, val, 0, siz);
}
void update(int L, int R, M val) {
if(L < 0) L = 0;
if(R > N) R = N;
assert(L < R);
upd__(L, R, 0, val, 0, siz);
}
T get(int idx) {
assert(0 <= idx && idx < N);
return get__(idx, idx + 1, 0, 0, siz);
}
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:
void eval(int idx) {
if(lazy[idx] == em) return;
if(idx < siz - 1) {
lazy[2 * idx + 1] = f_lz(lazy[2 * idx + 1], lazy[idx]);
lazy[2 * idx + 2] = f_lz(lazy[2 * idx + 2], lazy[idx]);
}
node[idx] = f_upd(node[idx], lazy[idx]);
lazy[idx] = em;
}
void upd__(int L, int R, int idx, M val, int l, int r) {
eval(idx);
if(r <= L || R <= l) return;
if(L <= l && r <= R) {
lazy[idx] = f_lz(lazy[idx], val);
eval(idx);
}
else {
upd__(L, R, 2 * idx + 1, val, l, (l + r) / 2);
upd__(L, R, 2 * idx + 2, val, (l + r) / 2, r);
node[idx] = op(node[2 * idx + 1], node[2 * idx + 2]);
}
}
T get__(int L, int R, int idx, int l, int r) {
if(r <= L || R <= l) return ex;
eval(idx);
if(L <= l && r <= R) return node[idx];
T vl = get__(L, R, 2 * idx + 1, l, (l + r) / 2);
T vr = get__(L, R, 2 * idx + 2, (l + r) / 2, r);
return op(vl, vr);
}
};
#line 2 "tree/segtree_lazy.cpp"
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
template<typename T, typename M> struct segtree_lazy {
using F = function<T(T, T)>;
using FU = function<T(T, M)>;
using FM = function<M(M, M)>;
private:
int siz = 1, N;
vector<T> node;
vector<M> lazy;
const F op;
const FU f_upd;
const FM f_lz;
const T ex;
const M em;
public:
segtree_lazy(int n, const F op, const FU f_upd, const FM f_lz, const T ex, const M em) :
N(n), op(op), f_upd(f_upd), f_lz(f_lz), ex(ex), em(em) {
while(siz < N) siz <<= 1;
node.resize(2 * siz - 1, ex);
lazy.resize(2 * siz - 1, em);
}
segtree_lazy(vector<T> &v, const F op, const FU f_upd, const FM f_lz, const T ex, const M em) :
N(v.size()), op(op), f_upd(f_upd), f_lz(f_lz), ex(ex), em(em) {
while(siz < N) siz <<= 1;
node.resize(2 * siz - 1, ex);
lazy.resize(2 * siz - 1, em);
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, M val) {
assert(0 <= idx && idx < N);
upd__(idx, idx + 1, 0, val, 0, siz);
}
void update(int L, int R, M val) {
if(L < 0) L = 0;
if(R > N) R = N;
assert(L < R);
upd__(L, R, 0, val, 0, siz);
}
T get(int idx) {
assert(0 <= idx && idx < N);
return get__(idx, idx + 1, 0, 0, siz);
}
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:
void eval(int idx) {
if(lazy[idx] == em) return;
if(idx < siz - 1) {
lazy[2 * idx + 1] = f_lz(lazy[2 * idx + 1], lazy[idx]);
lazy[2 * idx + 2] = f_lz(lazy[2 * idx + 2], lazy[idx]);
}
node[idx] = f_upd(node[idx], lazy[idx]);
lazy[idx] = em;
}
void upd__(int L, int R, int idx, M val, int l, int r) {
eval(idx);
if(r <= L || R <= l) return;
if(L <= l && r <= R) {
lazy[idx] = f_lz(lazy[idx], val);
eval(idx);
}
else {
upd__(L, R, 2 * idx + 1, val, l, (l + r) / 2);
upd__(L, R, 2 * idx + 2, val, (l + r) / 2, r);
node[idx] = op(node[2 * idx + 1], node[2 * idx + 2]);
}
}
T get__(int L, int R, int idx, int l, int r) {
if(r <= L || R <= l) return ex;
eval(idx);
if(L <= l && r <= R) return node[idx];
T vl = get__(L, R, 2 * idx + 1, l, (l + r) / 2);
T vr = get__(L, R, 2 * idx + 2, (l + r) / 2, r);
return op(vl, vr);
}
};