永続セグ木

完全二分木の葉に列を置き、各ノードにはその区間の値を op でまとめたものを持たせます。1 点を更新するときは、根からその葉までの道にあるノードだけをコピーして新しい根を作り、残りの部分木は前の版と共有します(経路コピー)。前の版はそのまま残り、どの版からでも新しい版を作れます。ノードはオブジェクトにせず、子の番号と値をリスト lch, rch, d に持たせています。

op と e は ACL のセグ木と同じで、op は結合的な演算(可換でなくてよい)、e はその単位元です。版の番号は整数で、最初の列が版 $0$ です。set を呼ぶたびに $1, 2, \dots$ と増えます。区間はすべて半開区間 $[l, r)$ です。

set 1 回でノードが $O(\log N)$ 個増えるので、 $Q$ 回更新したときのメモリは $O(N + Q \log N)$ です。

RangeKth(区間で $k$ 番目に小さい値):

値を座標圧縮して、版 $i$ が「 $a$ の先頭 $i$ 個に各値がいくつあるか」を持つ永続セグ木を作ります。 $a_l, \dots, a_{r-1}$ に各値がいくつあるかは版 $r$ と版 $l$ の差なので、2 つの版の根から同時に降りて、左の子の個数の差が $k$ より大きければ左へ、そうでなければその個数を $k$ から引いて右へ進みます。降りるときに見るのは左の子の個数だけなので、各ノードにはそれだけを持たせています。

区間で $k$ 番目に小さい値は Wavelet Matrix でも求められます(どちらも値の更新はできません)。Wavelet Matrix では、ある範囲に入る値の個数や和なども求められます。RangeKth は値を座標圧縮するので、負の値や大きな値もそのまま渡せます。

2 つのクラスは互いに使っていないので、使う方だけを貼れば動きます。

例:

seg = PersistentSegTree([3, 1, 4, 1, 5], lambda x, y: x + y, 0)
v1 = seg.set(0, 1, 9)  # 版 0 の a[1] を 9 にした版
v2 = seg.set(0, 4, 0)  # 版 0 から枝分かれ
print(seg.prod(0, 0, 5), seg.prod(v1, 0, 5), seg.prod(v2, 1, 5))  # 14 22 6
print(seg.get(v1, 1), seg.get(0, 1))  # 9 1

rk = RangeKth([5, 2, 8, 2, 7, 1])
print(rk.kth(1, 5, 0), rk.kth(1, 5, 2), rk.kth(0, 6, 5))  # 2 7 8

コード

class PersistentSegTree:
    # 経路コピーで永続化したセグ木(op は結合的、e はその単位元)。版の番号は 0, 1, 2, ...
    def __init__(self, a, op, e):
        n = len(a)
        self.n = n
        self.op = op
        self.e = e
        log = 0
        while (1 << log) < n:
            log += 1
        self.log = log
        size = 1 << log
        # 版 0 はヒープと同じ番号付け(ノード k の子は 2k と 2k + 1、葉 size + i が a[i])
        self.lch = list(range(0, 2 * size, 2)) + [0] * size
        self.rch = list(range(1, 2 * size, 2)) + [0] * size
        d = [e] * (2 * size)  # d[t] = ノード t の区間の値を op でまとめたもの
        d[size:size + n] = a
        for k in range(size - 1, 0, -1):
            d[k] = op(d[2 * k], d[2 * k + 1])
        self.d = d
        self.root = [1]  # root[v] = 版 v の根

    def set(self, ver, p, x):
        # 版 ver の a[p] を x にした新しい版を作り、その番号を返す(版 ver は変わらない)
        lch, rch, d = self.lch, self.rch, self.d
        t = self.root[ver]
        k = c = len(d)  # 根から順に、通るノードをコピーしたノード k, k + 1, ... を作る
        for j in range(self.log - 1, -1, -1):
            c += 1
            if p >> j & 1:
                lch.append(lch[t])
                rch.append(c)
                t = rch[t]
            else:
                lch.append(c)
                rch.append(rch[t])
                t = lch[t]
            d.append(x)  # 値はあとで計算し直す
        lch.append(0)
        rch.append(0)
        d.append(x)
        # 葉の親から根に向かって、区間の値を計算し直す
        op = self.op
        for u in range(c - 1, k - 1, -1):
            d[u] = op(d[lch[u]], d[rch[u]])
        self.root.append(k)
        return len(self.root) - 1

    def get(self, ver, p):
        # 版 ver の a[p]
        lch, rch = self.lch, self.rch
        t = self.root[ver]
        for j in range(self.log - 1, -1, -1):
            t = rch[t] if p >> j & 1 else lch[t]
        return self.d[t]

    def prod(self, ver, l, r):
        # 版 ver の op(a[l], ..., a[r - 1])(l == r なら e)
        if l >= r:
            return self.e
        lch, rch, d, op = self.lch, self.rch, self.d, self.op
        r -= 1  # 両端を含む [l, r] にする
        j = (l ^ r).bit_length() - 1  # l と r が分かれる桁
        t = self.root[ver]
        for i in range(self.log - 1, j, -1):  # l と r が同じ子に入る間はそちらに進む
            t = rch[t] if l >> i & 1 else lch[t]
        if j < 0:
            return d[t]
        # l は左の子から、r は右の子から葉まで降りながら、間にある部分木の値をまとめる
        sl = sr = self.e
        u = lch[t]
        v = rch[t]
        for i in range(j - 1, -1, -1):
            if l >> i & 1:
                u = rch[u]
            else:
                sl = op(d[rch[u]], sl)
                u = lch[u]
            if r >> i & 1:
                sr = op(sr, d[lch[v]])
                v = rch[v]
            else:
                v = lch[v]
        return op(op(d[u], sl), op(sr, d[v]))


class RangeKth:
    # a[l:r] の小さい方から k 番目の値を求める
    # 版 i が a[:i] の各値(座標圧縮したもの)の個数を持つ永続セグ木を使う
    def __init__(self, a):
        self.vals = sorted(set(a))
        idx = {x: i for i, x in enumerate(self.vals)}
        log = 0
        while (1 << log) < len(self.vals):
            log += 1
        self.log = log
        # 降りるときに見るのは左の子の個数だけなので、各ノードにはそれを持たせる
        # ノード 0 は個数がすべて 0 の木(子も自分自身)
        lch = [0]
        rch = [0]
        lc = [0]  # lc[t] = ノード t の左の子の区間に入る値の個数(葉は 0)
        root = [0]  # root[i] = 版 i の根
        for x in a:
            p = idx[x]
            t = root[-1]
            c = len(lc)  # 根から順に、通るノードをコピーしたノード c, c + 1, ... を作る
            root.append(c)
            for j in range(log - 1, -1, -1):
                c += 1
                if p >> j & 1:
                    lc.append(lc[t])
                    lch.append(lch[t])
                    rch.append(c)
                    t = rch[t]
                else:
                    lc.append(lc[t] + 1)
                    lch.append(c)
                    rch.append(rch[t])
                    t = lch[t]
            lc.append(0)
            lch.append(0)
            rch.append(0)
        self.lch = lch
        self.rch = rch
        self.lc = lc
        self.root = root

    def kth(self, l, r, k):
        # a[l:r] の小さい方から k 番目(0-indexed)の値
        # 版 r と版 l の根から同時に降り、左の子の個数の差で進む向きを決める
        lch, rch, lc = self.lch, self.rch, self.lc
        u = self.root[l]
        v = self.root[r]
        p = 0
        for j in range(self.log - 1, -1, -1):
            c = lc[v] - lc[u]  # a[l:r] のうち左の子に入る値の個数
            if k < c:
                u = lch[u]
                v = lch[v]
            else:
                k -= c
                u = rch[u]
                v = rch[v]
                p += 1 << j
        return self.vals[p]