動的セグ木

列の長さ $n$ が大きく( $10^{18}$ 程度まで)、普通のセグ木では配列を用意できないときに使います。高さ $\lceil \log_2 n \rceil$ の完全二分木を考え、set で値を置くときに、根からその葉までの道にあるノードのうち、まだないものだけを作ります。まだ作っていない部分木の値はすべて e なので、ノード $0$ を「値が e の空の部分木」として、子がないところはノード $0$ を指すようにしています。ノードはオブジェクトにせず、子の番号と値をリスト lch, rch, d に持たせ、再帰は使いません。

op と e は ACL のセグ木と同じで、op は結合的な演算(可換でなくてよい)、e はその単位元です。最初はすべての値が e です。区間はすべて半開区間 $[l, r)$ です。

max_right に渡す f は、f(e) が True で、区間を広げると True から False に変わることはあっても、False から True には戻らないものとします(ACL のセグ木と同じです)。

set を $Q$ 回呼んだときのメモリは $O(Q \log n)$ です。クエリがすべて前もってわかっているときは、使う添字を 座標圧縮 して普通のセグ木(ACL の SegTree)を使う方が、速くてメモリも少なく済みます。

例:

n = pow(10, 18)
seg = DynamicSegTree(n, lambda x, y: x + y, 0)
seg.set(3, 5)
seg.set(pow(10, 17), 2)
seg.set(n - 1, 7)
print(seg.prod(0, n), seg.prod(4, n - 1), seg.get(3), seg.get(4))  # 14 2 5 0

例( $0$ 以上 $10^{18}$ 未満の整数の多重集合で、小さい方から $k$ 番目の値):

cnt = DynamicSegTree(pow(10, 18), lambda x, y: x + y, 0)  # cnt[v] = v の個数
for v in [5, pow(10, 17), 5, 42]:
    cnt.set(v, cnt.get(v) + 1)
k = 2  # 0-indexed
print(cnt.max_right(0, lambda s: s <= k))  # 42(v 以下の個数が k より多くなる最小の v)

コード

class DynamicSegTree:
    # 添字 0 <= i < n(n は 10^18 程度まででよい)の列で、触ったノードだけを作るセグ木
    # op は結合的な演算(可換でなくてよい)、e はその単位元。最初はすべて e
    def __init__(self, n, op, e):
        self.n = n
        self.op = op
        self.e = e
        log = 0
        while (1 << log) < n:
            log += 1
        self.log = log
        # 高さ log の完全二分木で、根はノード 1、根から p の桁を上から見て降りた葉が a[p]
        # ノード 0 は「まだ作っていない部分木」(値は e で、子も 0)
        self.lch = [0, 0]  # 左の子(なければ 0)
        self.rch = [0, 0]  # 右の子(なければ 0)
        self.d = [e, e]  # d[t] = ノード t の区間の値を op でまとめたもの

    def set(self, p, x):
        # a[p] を x にする(通るノードがなければ作る)
        lch, rch, d = self.lch, self.rch, self.d
        path = []
        t = 1
        for j in range(self.log - 1, -1, -1):
            path.append(t)
            ch = rch if p >> j & 1 else lch
            c = ch[t]
            if not c:
                c = ch[t] = len(d)
                lch.append(0)
                rch.append(0)
                d.append(self.e)
            t = c
        d[t] = x
        # 葉の親から根に向かって計算し直す
        op = self.op
        for t in reversed(path):
            d[t] = op(d[lch[t]], d[rch[t]])

    def get(self, p):
        # a[p] の値(ノードがなければ e)
        lch, rch = self.lch, self.rch
        t = 1
        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, l, r):
        # 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 = 1
        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:
                c = rch[u]
                if c:
                    sl = op(d[c], sl)
                u = lch[u]
            if r >> i & 1:
                c = lch[v]
                if c:
                    sr = op(sr, d[c])
                v = rch[v]
            else:
                v = lch[v]
        return op(op(d[u], sl), op(sr, d[v]))

    def max_right(self, l, f):
        # f(op(a[l], ..., a[r - 1])) が True になる最大の r(f(e) は True で、ACL と同じ)
        if l >= self.n:
            return self.n
        lch, rch, d, op = self.lch, self.rch, self.d, self.op
        # 根から葉 l へ降りながら、右側にある部分木とその高さを集める
        nodes = []
        hs = []
        t = 1
        for i in range(self.log - 1, -1, -1):
            if l >> i & 1:
                t = rch[t]
            else:
                nodes.append(rch[t])
                hs.append(i)
                t = lch[t]
        nodes.append(t)
        hs.append(0)
        # 葉 l から右へ、部分木を順に足していく
        s = self.e
        p = l
        for k in range(len(nodes) - 1, -1, -1):
            t = nodes[k]
            x = op(s, d[t])
            if f(x):
                s = x
                p += 1 << hs[k]
                continue
            # この部分木の中で、f が False になる最初の葉を探す
            for i in range(hs[k] - 1, -1, -1):
                x = op(s, d[lch[t]])
                if f(x):
                    s = x
                    p += 1 << i
                    t = rch[t]
                else:
                    t = lch[t]
            return p
        return self.n