双対セグ木

値は葉（元の列）に置いたままにして、各ノードには、そのノードの区間全体にまだ配っていない作用を持たせます。1 点の値は、葉から根までの作用を合成して、元の値に作用させたものです。区間に作用させる前に、上のノードの作用を子に配っておくので、区間更新や区間アフィン変換のように、作用の順番で結果が変わるもの（可換でないもの）にも使えます。

作用の渡し方は ACL の 遅延セグ木 と同じです。遅延セグ木でも同じことはできますが、区間の値をまとめる演算 op と単位元 e を用意して、作用がそれと両立するようにしなければなりません。1 点の値だけでよいときは、こちらの方が渡すものが少なく、速いです。

DualSegTree(a, mapping, composition, id_) に渡すもの:

• a: 初期の列
• mapping(f, x): 作用 $f$ を値 $x$ に作用させた結果
• composition(f, g): 作用 $g$ のあとに $f$ をすること（ $f \circ g$）を 1 つの作用にしたもの。 $f$ が新しく来た方
• id_: 何もしない作用

メソッド:

• apply(l, r, f): $l \le i < r$ の各 $a_i$ に $f$ を作用させる。 $O(\log N)$
• get(p): $a_p$ の今の値。 $O(\log N)$
• set(p, x): $a_p$ を $x$ にする。 $O(\log N)$

例:

# 区間加算・1 点取得
seg = DualSegTree(a, lambda f, x: f + x, lambda f, g: f + g, 0)
seg.apply(l, r, x)  # a[l:r] の各値に x を足す
y = seg.get(p)  # a[p]

# 区間 chmin・1 点取得
INF = 1 << 60
seg = DualSegTree(a, min, min, INF)
seg.apply(l, r, x)  # a[l:r] の各値を min(値, x) にする

# 区間更新・1 点取得（作用 None は何もしない）
mapping = lambda f, x: x if f is None else f
composition = lambda f, g: g if f is None else f
seg = DualSegTree(a, mapping, composition, None)
seg.apply(l, r, x)  # a[l:r] をすべて x にする

コード

class DualSegTree:
    # 区間に作用を適用し、1 点の値を求める（作用の渡し方は ACL の lazy_segtree と同じ）
    # mapping(f, x): f を x に作用させた値 / composition(f, g): g のあとに f をする作用
    def __init__(self, a, mapping, composition, id_):
        self.n = len(a)
        self.a = list(a)  # 値は葉に置いたまま
        self.mapping = mapping
        self.composition = composition
        self.id = id_
        self.log = 0
        while (1 << self.log) < self.n:
            self.log += 1
        self.size = 1 << self.log
        self.lz = [id_] * (2 * self.size)  # lz[k] = ノード k の区間にまだ配っていない作用

    def _push(self, k):
        # ノード k の作用を子に配る
        lz = self.lz
        f = lz[k]
        lz[2 * k] = self.composition(f, lz[2 * k])
        lz[2 * k + 1] = self.composition(f, lz[2 * k + 1])
        lz[k] = self.id

    def apply(self, l, r, f):
        # l <= i < r の各 a[i] に f を作用させる
        if l == r:
            return
        l += self.size
        r += self.size
        # 作用が可換でなくてもよいように、先に上のノードの作用を配っておく
        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self._push(l >> i)
            if ((r >> i) << i) != r:
                self._push((r - 1) >> i)
        lz = self.lz
        comp = self.composition
        while l < r:
            if l & 1:
                lz[l] = comp(f, lz[l])
                l += 1
            if r & 1:
                r -= 1
                lz[r] = comp(f, lz[r])
            l >>= 1
            r >>= 1

    def get(self, p):
        # a[p] の今の値（葉から根までの作用を合成して作用させる）
        lz = self.lz
        k = p + self.size
        f = lz[k]
        k >>= 1
        while k:
            f = self.composition(lz[k], f)
            k >>= 1
        return self.mapping(f, self.a[p])

    def set(self, p, x):
        # a[p] を x にする
        k = p + self.size
        for i in range(self.log, 0, -1):
            self._push(k >> i)
        self.lz[k] = self.id
        self.a[p] = x