Segment Tree Beatsの実装メモ (Historic Informationまわり)
Segment Tree Beats(SGT Beats)のHistoric Informationまわりについて自分が理解した範囲のメモ
この記事は以下の続き。これらの説明を前提に書いてある。
また、以下を参考にしてこの記事を書いている。
- A simple introduction to "Segment tree beats" - Codeforces (Task 5, Task 6あたり)
- 区间最值操作与历史最值问题 - 道客巴巴 (主に4.4, 4.5あたり)
目次
- Historic Information
- historic maximal/minimal valueを管理する考え方
- historic sumを管理する考え方
- 区間chmax(chmin)クエリを含むhistoric maximal valueを扱う
- 区間chmin/chmaxクエリを同時に処理するhistoric maximal valueを扱う
- RUQを含むhistoric informationを処理する
- 関連問題
Historic Information
Segment Tree Beatsで処理できるものにHistoric Informationがある。
に対する区間加算クエリや区間chmin/chmaxクエリを処理しながら以下を処理できる。
従来の遅延セグ木でもある程度であれば実現できる。例えば、以下のようにhistoric maximal valueの区間最大値を管理することができる(区間chmaxクエリも処理できる)。
historic maximal/minimal valueを管理する考え方
historic maximal valueについて扱う。historic minimal valueも同様の考え方で解くことができる。
以下の問題を考える。
長さの数列が与えられる。また、最初は数列と等しい数列がある。
以下のクエリを合計回処理せよ。
- について を に更新
- を出力
- を出力
各クエリ後、各 は に更新される。
制約:
この問題では各のhistoric maximal valueであるを管理する必要がある。
このの代わりに、過去最大値と現在値の差分()の列 を管理することを考える。
(下の図の白い部分が、橙色の部分がに該当する)
すると、 に を加算する際に を に更新するのみになる。
(Segment Tree Beats上では区間加算クエリ → 区間chmaxクエリで処理すればよいため簡単に処理できる)
全体の計算量は
区間最大値クエリ(RMQ)の処理
この問題ではhistoric maximal valueの区間最大値を直接管理しても解ける。(区間総和がなければ)
ここでは、をベースに管理することを考えてみる。
historic maximal valueの区間最大値は
を求めることになる。
この区間最大値は前回の例題のTask4と同じ感じで処理することができ、各ノードで以下の区間情報を持たせることで解くことができる。
- が最小値となる の中の の最大値
- 最小値の をchmaxで更新する際に加算処理が行われる
- が非最小値となる の中の の最大値
同様の考え方で の区間最小値クエリも処理できる。
実装
実装コード(Gist): Segment Tree Beats (Historic Informationまわり) の実装 · GitHub
historic sumを管理する考え方
以下のような問題を考える。
長さの数列が与えられる。また、最初は数列と等しい数列がある。
以下のクエリを合計回処理せよ。
- について を に更新
- を出力
各クエリ後、各 は に更新される。
制約:
現在処理しているクエリ番号を ()とする。
historic sumを管理するために、数列とは別に、各について を満たす数列を管理することを考える。
番目が区間加算クエリで を に更新した場合、 が に更新されるため、これに合うように を に更新すればよい。
この の更新は区間加算操作によって実現できる。
また、番目で区間総和クエリ(RSQ)を処理する場合、
で求められるため、(上のRSQ) × + (上のRSQ)で求めることができる。
この問題では、数列と数列に対してRAQとRSQができれば十分である。そのため、2つの数列に対してRAQとRSQを処理できる従来の遅延セグ木 もしくは BIT で解くことができる。
計算量は
実装
実装コード(Gist): Segment Tree Beats (Historic Informationまわり) の実装 · GitHub
区間chmax(chmin)クエリを含むhistoric maximal valueを扱う
以下のような問題を考える。
長さの数列が与えられる。以下のクエリを合計回処理せよ。
- について を に更新
- について を に更新
- を出力
- を出力
各クエリ後、各 は に更新される。
制約:
今回も前の例のように数列の値に加え、 (過去最大値) - (現在値)を示す数列の値を管理する。
この問題では、数列に対して以下の処理を実現する必要がある
問題は(2)の処理であり、に対し区間chmaxクエリを処理する際に (最小値) < x < (二番目の最小値) を満たす各ノードにおいて が最小となる全ての のみに 加算とchmax を行う必要がある。
そのため、前の例のように各ノードで単に の最小値・二番目の最小値 を管理するだけではうまく更新できない。
そこで、 が最小値となる のみを更新できるように、各ノードにおいて が最小値となる場合と が非最小値となる場合とで の区間情報を分けて管理することを考える。
具体的に、各ノードに以下の区間情報をもたせる。
- が最小値となる の中での、 の最小値、二番目のの最小値、最小値の個数
- が非最小値となる の中での、 の最小値、二番目のの最小値、最小値の個数
ここで具体的な例で考えてみる。以下の図は今回の例とするセグ木である。
各ノードには の最小値・二番目の最小値が書かれてある。(この後の図では の最小値を省略するので、分かりやすさのために が最小値が同じ箇所を同じ色で塗り分けてある)
そして、以下の図は の要素を の最小値・非最小値で分けて管理する例である。 が最小値の場合(青枠)と非最小値の場合(緑枠)で分けて の最小値・二番目の最小値を管理するイメージである。
各枠の"x/y"はxが最大値、yが二番目の最大値(yが書かれてない場合は )を示す。枠が存在しない場合はx,yそれぞれ を示す。
このように管理することで、区間chmaxクエリも処理できるようになる。
実際に各操作クエリでは以下の処理を行えばよい
- 区間加算操作(, )を行う
- を で更新する
- が最小値となる 、 が非最小値となる それぞれについて
(の最小値) < 0 < (の二番目の最小値) を満たすノードまで探索して の最小値を 0 で更新する
- が最小値となる 、 が非最小値となる それぞれについて
ここで、例のセグ木を で更新する例を考える。
初めに
この加算操作の後、更に(が最小値・非最小値の場合それぞれで)
全体の計算量は になることが示せる。
区間最大値クエリ(RMQ)の処理
区間chmaxクエリを含まない例題と同じように各ノードで の値を(が最小値・非最小値で分けて)管理する。
今回は区間chmaxクエリで処理できるように、が最小値・非最小値の場合に分けた上でが最小値・非最小値の場合で分けて管理する。
以下の図は の最大値を管理するイメージを示したもの。が最小値(青枠)と非最小値(緑枠)の中それぞれで、 が最小値/非最小値の時の の最大値を保持する。
各枠の"x/y"は x が が最小値の時、yが が非最小値の時の の最大値を示す。(書かれてない場合は を表す)
この問題の区間総和がなければ、従来の遅延セグ木でうまくマージできるlazy tagを定義できるためで解くことができる。もしlazy tagがうまくマージできない場合(今回の問題が区間chminクエリだった場合等)でも、現在の最大値とhistoric maximal valueを が最大値の場合・が非最大値の場合、等で分けて管理することで で解くことができる。
実装
各ノードが持つ区間情報
// d_i まわりの情報を管理する構造体 // 各ノードごとに、この構造体を a_i が最小値の場合・a_i が非最小値の場合 で2つ持つ struct HistVal { // min_v: d_i の最小値 // smin_v: 二番目の最小値 // min_c: 最小値の個数 // sum: d_iの総和 ll min_v, smin_v, min_c, sum; // m_hmax: d_i が最小値の a_i + d_i の最大値 // nm_hmax: d_i が非最小値の a_i + d_i の最大値 ll m_hmax, nm_hmax; // ... // d_i の最小値を x に更新 // pushdown, chmaxの際に使う void update_min(ll x) { if(min_v < x) { sum += (x - min_v) * min_c; // a_i + d_i の最大値はここのみで変化する m_hmax += (x - min_v); min_v = x; } } // l と r の2つの d_i の情報をマージして更新 // updateの際に使う // (l もしくは r に自身を指定しても問題ないように実装してある) void merge(HistVal &l, HistVal &r) { sum = l.sum + r.sum; nm_hmax = max(l.nm_hmax, r.nm_hmax); if(l.min_v < r.min_v) { smin_v = min(l.smin_v, r.min_v); min_v = l.min_v; min_c = l.min_c; nm_hmax = max(nm_hmax, r.m_hmax); m_hmax = l.m_hmax; } else if(l.min_v > r.min_v) { smin_v = min(l.min_v, r.smin_v); min_v = r.min_v; min_c = r.min_c; nm_hmax = max(nm_hmax, l.m_hmax); m_hmax = r.m_hmax; } else { min_v = l.min_v; smin_v = min(l.smin_v, r.smin_v); min_c = l.min_c + r.min_c; m_hmax = max(l.m_hmax, r.m_hmax); } } // 要素にxを加算 void add(ll x) { if(min_v != inf) min_v += x; if(smin_v != inf) smin_v += x; } // a_i + d_i の区間最大値を返す ll hmax() { return max(m_hmax, nm_hmax); } }; // min_d: a_i が最小値の i における d_i まわりの情報 // nmin_d: a_i が非最小値の i における d_i まわりの情報 HistVal min_d[4*N], nmin_d[4*N]; // 区間加算クエリ用 (ladd: lazy tag, len: 区間要素数) ll len[4*N], ladd[4*N]; // a_i の最小値・二番目の最小値・最小値の個数 ll min_v[4*N], smin_v[4*N], min_c[4*N]; // a_i の区間総和 ll sum[4*N]; // ノードk の // - b_i の区間総和: sum[k] + min_d[k].sum + nmin_d[k].sum // - b_i の区間最大値: max(min_d[k].hmax(), nmin_d[k].hmax())
区間chmaxクエリを処理するための実装
// a_i の最小値を x に更新する void update_node_min(int k, ll x) { // a_i の区間総和の更新 sum[k] += (x - min_v[k]) * min_c[k]; // d_i に関する情報の更新 // a_i が最小値となる場合の d_i を更新 min_d[k].add(min_v[k] - x); min_d[k].sum += (min_v[k] - x) * min_c[k]; min_v[k] = x; } // 区間[a, b) の a_i を max(a_i, x) に更新 void _update_max(ll x, int a, int b, int k, int l, int r) { if(b <= l || r <= a || x <= min_v[k]) { return; } if(a <= l && r <= b && x < smin_v[k]) { update_node_min(k, x); // d_i の値を max(d_i, 0) で更新 _update_dmax(k, l, r); return; } push(k); _update_max(x, a, b, 2*k+1, l, (l+r)/2); _update_max(x, a, b, 2*k+2, (l+r)/2, r); update(k); }
区間加算クエリを処理するための実装
void addall(int k, ll a) { // a_i に関する情報を更新 min_v[k] += a; if(smin_v[k] != inf) smin_v[k] += a; sum[k] += a * len[k]; // d_i に関する情報を更新 // a_i が最小値の場合・非最小値の場合、両方の d_i を更新 min_d[k].add(-a); nmin_d[k].add(-a); min_d[k].sum -= a * min_c[k]; nmin_d[k].sum -= a * (len[k] - min_c[k]); // 遅延させている値の更新 ladd[k] += a; } // 区間[a, b) の a_i を a_i + x に更新 void _add_val(ll x, int a, int b, int k, int l, int r) { if(b <= l || r <= a) { return; } if(a <= l && r <= b) { addall(k, x); // d_i の値を max(d_i, 0) で更新 _update_dmax(k, l, r); return; } push(k); _add_val(x, a, b, 2*k+1, l, (l+r)/2); _add_val(x, a, b, 2*k+2, (l+r)/2, r); update(k); }
d_i に対する区間chmax更新処理
DFS中の条件は以下のように設定すればよい
- break condition: が最大値・非最大値の場合両方で 0 ≤ (の最小値) を満たす
- tag condition: が最大値・非最大値の場合両方で0 < (の二番目の最小値) を満たす
// (内部用) d_i <- max(d_i, 0) で更新 void _update_dmax(int k, int l, int r) { // break condition: 以下の条件を満たすこと // - a_i が最小値である d_i の最小値(min_d[k].min_v)が0以上 // - a_i が非最小値である d_i の最小値(nmin_d[k].min_v)が0以上 if(l == r || (0 <= min_d[k].min_v && 0 <= nmin_d[k].min_v)) { return; } // tag condition: 以下の条件を満たすこと // - a_i が最小値である d_i の二番目の最小値(min_d[k].smin_v)が0より大きい // - a_i が非最小値である d_i の二番目の最小値(nmin_d[k].smin_v)が0より大きい if(0 < min_d[k].smin_v && 0 < nmin_d[k].smin_v) { // d_i の最小値を 0 に更新する min_d[k].update_min(0); nmin_d[k].update_min(0); return; } push(k); _update_dmax(2*k+1, l, (l+r)/2); _update_dmax(2*k+2, (l+r)/2, r); update(k); }
pushdown処理
が最小値の場合・非最小値の場合で情報を分けて管理しているため、正しく伝搬を行う。
が最小値の場合の の最小値は、左右の子ノードで が最小値となる方に伝搬する。
それ以外は が非最小値の場合の の最小値を伝搬する。
void push(int k) { if(ladd[k] != 0) { addall(2*k+1, ladd[k]); addall(2*k+2, ladd[k]); ladd[k] = 0; } if(min_v[2*k+1] < min_v[k]) { update_node_min(2*k+1, min_v[k]); } if(min_v[2*k+2] < min_v[k]) { update_node_min(2*k+2, min_v[k]); } // 子ノードにおける a_i が最小値の場合の d_i の最小値に、ノードkの d_i の最小値情報を伝搬 // - 子ノードにおける a_i の最小値の大小関係によって、 // どちらの d_i の最小値(min_d[k].min_v, nmin_d[k].min_v)を伝搬するか決める if(min_v[2*k+1] < min_v[2*k+2]) { min_d[2*k+1].update_min(min_d[k].min_v); min_d[2*k+2].update_min(nmin_d[k].min_v); } else if(min_v[2*k+1] > min_v[2*k+2]) { min_d[2*k+1].update_min(nmin_d[k].min_v); min_d[2*k+2].update_min(min_d[k].min_v); } else { // min_v[2*k+1] == min_v[2*k+2] min_d[2*k+1].update_min(min_d[k].min_v); min_d[2*k+2].update_min(min_d[k].min_v); } // a_i の非最小値の場合の d_i の最小値に情報を伝搬 nmin_d[2*k+1].update_min(nmin_d[k].min_v); nmin_d[2*k+2].update_min(nmin_d[k].min_v); }
update処理
が最小値の場合の の情報は、左右の子ノードの内 の最小値を持つ方のノードから持ってくる。
それ以外の情報は が非最小値となる場合の の情報としてマージする。
void update(int k) { sum[k] = sum[2*k+1] + sum[2*k+2]; nmin_d[k].merge(nmin_d[2*k+1], nmin_d[2*k+2]); if(min_v[2*k+1] < min_v[2*k+2]) { min_v[k] = min_v[2*k+1]; min_c[k] = min_c[2*k+1]; smin_v[k] = min(smin_v[2*k+1], min_v[2*k+2]); min_d[k] = min_d[2*k+1]; nmin_d[k].merge(nmin_d[k], min_d[2*k+2]); } else if(min_v[2*k+1] > min_v[2*k+2]) { min_v[k] = min_v[2*k+2]; min_c[k] = min_c[2*k+2]; smin_v[k] = min(min_v[2*k+1], smin_v[2*k+2]); min_d[k] = min_d[2*k+2]; nmin_d[k].merge(nmin_d[k], min_d[2*k+1]); } else { // min_v[2*k+1] == min_v[2*k+2] min_v[k] = min_v[2*k+1]; min_c[k] = min_c[2*k+1] + min_c[2*k+2]; smin_v[k] = min(smin_v[2*k+1], smin_v[2*k+2]); min_d[k].merge(min_d[2*k+1], min_d[2*k+2]); } }
実装全体
実装コード(Gist): Segment Tree Beats (Historic Informationまわり) の実装 · GitHub
区間chmin/chmaxクエリを同時に処理するhistoric maximal valueを扱う
長さの数列が与えられる。以下のクエリを合計回処理せよ。
- について を に更新
- について を に更新
- について を に更新
- を出力
- を出力
各クエリ後、各 は に更新される。
制約:
区間chmin/chmaxクエリを扱う場合は、情報を分けて管理する考え方に基づき、3種類に分けて管理すればよい。
具体的に、については以下のように情報を分けて管理する。
- が最小値の場合の の最小値、二番目のの最小値、の最小値の数
- が最大値の場合の の最小値、二番目のの最小値、の最小値の数
- が非最小値かつ非最大値の場合の の最小値、二番目のの最小値、の最小値の数
このように管理することで、区間chmin/chmaxクエリ両方を同時に処理できるようになる。
実装
実装コード(Gist): Segment Tree Beats (Historic Informationまわり) の実装 · GitHub