Day 053-Q2 | 永続BIT（Persistent Fenwick Tree + オフライン区間k番目クエリ）

問題

長さ $N$ の整数列 $A = (A_1, \ldots, A_N)$ と $Q$ クエリが与えられる。

type 1: 1 i x — $A_i$ を $x$ に変更（新バージョンを作成）
type 2: 2 l r k v — バージョン $v$ での $[l, r]$ の $k$ 番目に小さい値を出力

バージョン 0 = 初期状態。type 1 クエリごとにバージョンが1増える。

制約

パラメータ	範囲
$N$	$1 \le N \le 2 \times 10^5$
$Q$	$1 \le Q \le 10^5$
$A_i, x$	$1 \le A_i, x \le 10^9$
$l, r$	$1 \le l \le r \le N$
$k$	$1 \le k \le r - l + 1$
$v$	$0 \le v \le$ 現在バージョン数

入出力例

入力例 1

出力例 1

1
1
1

v0=[3,1,4,1,5] の [1,5] 2番目=1。v1=[3,1,2,1,5]（A_3←2）の [1,5] 2番目=1。v1 の [2,4]=[1,2,1] の1番目=1。

概念図: 永続セグメント木の構造

ヒント（段階的開示）

ヒント1: 方向性

永続セグメント木を使い、値軸（座標圧縮後）の頻度を prefix として管理する。$\text{prefix\_root}[v][i]$ = バージョン $v$ での $[1..i]$ の頻度 SegTree の root。区間 $[l, r]$ のクエリは $[1,r]$ と $[1,l-1]$ の差分で二分探索する。

ヒント2: アプローチ

全クエリを先読みして座標圧縮（type 1 の更新値も含む）
prefix 永続SegTree: $\text{root}[v][i]$ = バージョン $v$ での $[1..i]$ の根
type 1 クエリ: $A_i$ を消して $x$ を追加 → $i$ 以降のすべての prefix root を $O(\log M)$ ずつ更新
type 2 クエリ: $\text{query\_kth}(\text{root}[v][r], \text{root}[v][l-1], k)$ を $O(\log M)$ で処理

ヒント3: コード骨格

# nodes[i] = [left, right, count]
nodes = [[0, 0, 0]]  # 0 = null sentinel

def update(prev, lo, hi, pos, delta):
    cur = len(nodes)
    nodes.append(list(nodes[prev]))
    nodes[cur][2] += delta
    if hi - lo == 1: return cur
    mid = (lo + hi) // 2
    if pos < mid:
        nodes[cur][0] = update(nodes[prev][0], lo, mid, pos, delta)
    else:
        nodes[cur][1] = update(nodes[prev][1], mid, hi, pos, delta)
    return cur

def query_kth(r_root, l_root, lo, hi, k):
    if hi - lo == 1: return lo
    mid = (lo + hi) // 2
    left_cnt = nodes[nodes[r_root][0]][2] - nodes[nodes[l_root][0]][2]
    if k <= left_cnt:
        return query_kth(nodes[r_root][0], nodes[l_root][0], lo, mid, k)
    return query_kth(nodes[r_root][1], nodes[l_root][1], mid, hi, k - left_cnt)

模範解答 (Python)

import sys
from bisect import bisect_left
input = sys.stdin.readline
sys.setrecursionlimit(300000)

def solve():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    queries = [list(map(int, input().split())) for _ in range(Q)]

    # 座標圧縮（更新値も含む）
    vals = sorted(set(A) | {q[2] for q in queries if q[0] == 1})
    M = len(vals)
    comp = {v: i for i, v in enumerate(vals)}

    # 永続SegTree（値軸）
    nodes = [[0, 0, 0]]  # sentinel

    def new_node(l, r, c):
        nodes.append([l, r, c])
        return len(nodes) - 1

    def update(prev, lo, hi, pos, delta):
        cur = new_node(nodes[prev][0], nodes[prev][1], nodes[prev][2] + delta)
        if hi - lo == 1: return cur
        mid = (lo + hi) // 2
        if pos < mid:
            nodes[cur][0] = update(nodes[prev][0], lo, mid, pos, delta)
        else:
            nodes[cur][1] = update(nodes[prev][1], mid, hi, pos, delta)
        return cur

    def kth(r_root, l_root, lo, hi, k):
        if hi - lo == 1: return lo
        mid = (lo + hi) // 2
        lc = nodes[nodes[r_root][0]][2] - nodes[nodes[l_root][0]][2]
        if k <= lc:
            return kth(nodes[r_root][0], nodes[l_root][0], lo, mid, k)
        return kth(nodes[r_root][1], nodes[l_root][1], mid, hi, k - lc)

    # prefix_roots[v][i] = バージョンv での [1..i] の SegTree root
    # 初期構築（v=0）
    prefix_roots = [[0] * (N + 1)]
    for i in range(N):
        prefix_roots[0][i+1] = update(prefix_roots[0][i], 0, M, comp[A[i]], 1)

    cur_A = A[:]
    cur_ver = 0
    results = []

    for q in queries:
        if q[0] == 1:
            _, i, x = q
            i -= 1  # 0-indexed
            old_c = comp[cur_A[i]]
            new_c = comp[x]
            cur_A[i] = x
            # 新バージョンのprefix rootsを構築（i以降を更新）
            prev_pr = prefix_roots[cur_ver]
            new_pr = prev_pr[:i+1][:]
            for j in range(i, N):
                # prev_pr[j+1]から old_c を削除、new_c を追加
                r = update(new_pr[-1], 0, M, old_c, -1)
                # 実際の値（インデックスj）を加算
                # ※ 簡略実装: 完全な実装はO(N log M)の再構築
                new_pr.append(update(prev_pr[j+1], 0, M, old_c, -1) if j == i else prev_pr[j+1])
            # 点更新のみ修正
            new_pr2 = prev_pr[:]
            for j in range(i+1, N+1):
                new_pr2[j] = update(
                    update(prev_pr[j], 0, M, old_c, -1),
                    0, M, new_c, 1
                )
            prefix_roots.append(new_pr2)
            cur_ver += 1
        else:
            _, l, r, k, v = q
            r_root = prefix_roots[v][r]
            l_root = prefix_roots[v][l-1]
            idx = kth(r_root, l_root, 0, M, k)
            results.append(vals[idx])

    print('\n'.join(map(str, results)))

solve()

Step-by-Step 解説

1永続SegTree の基本原理
通常のSegTree更新は $O(\log N)$ ノードを書き換える。永続化では書き換え先を新規作成し、古いバージョンを保持。空間 $O((N + Q) \log M)$、新バージョン作成 $O(\log M)$。

2座標圧縮
値の範囲が $10^9$ なので出現値をソートして圧縮。type 1 の更新値も含めて全値を事前収集する。

3prefix 永続SegTree による k番目クエリ
$\text{prefix\_root}[v][i]$ = バージョン $v$ での $[1..i]$ の頻度管理 root。$[l,r]$ の k番目は $[1,r]$ と $[1,l-1]$ の差分で左子の count を比べながら葉まで降りる。

4点更新（バージョン管理）
$A_i$ を $x$ に変えると、$\text{prefix\_root}[v][j]$ ($j > i$) すべてに影響。$A_i$ 分を削除 ($-1$) し $x$ 分を追加 ($+1$) した新 root を作る。

計算量

初期構築: $O(N \log M)$ 時間・空間
type 1 クエリ: $O(N \log M)$ — $i$ 以降のすべての prefix を更新
type 2 クエリ: $O(\log M)$ — 二分探索
全体: $O((N + Q) N \log M)$ — type 1 が多いと遅い
最適化: CDQ分割統治やWavelet Treeで O((N+Q) log N) に改善可能

よくあるミス

ミス	原因	正しい書き方
null ノードを 0 番にしない	子が存在しないとき参照エラー	`nodes[0] = [0, 0, 0]` でセンチネル
更新値を圧縮に含め忘れ	type 1 の x が圧縮範囲外になる	全クエリ先読みして圧縮
r と l-1 の root を逆に引く	差分の符号が逆になる	`nodes[r_root][cnt] - nodes[l_root][cnt]`
再帰深度超過	log M ≈ 18 なら問題ないが安全のため	`sys.setrecursionlimit(300000)`

次のステップ

発展問題: Wavelet Tree（静的配列の区間k番目を $O(\log M)$ で処理、空間 $O(N \log M)$）
関連: 永続SegTree + Euler Tour で部分木クエリを永続管理
応用: オフライン処理 + CDQ分割統治で点更新区間k番目を $O((N+Q)\log^2 N)$

自己評価

完全理解おおむね理解要復習