x. Dynamic DP

If a DP’s transition from the previous state is linear in a semiring ($(+,\times )$, $(\max ,+)$, $(\min ,+)$, $(\vee ,\wedge )$), then the DP is a product of small matrices, and a segment tree over the matrices supports point changes to the input in $O(k^3\log n)$. On trees, split off the heavy child: the transition from the heavy child is a matrix that depends on the light children’s results, and HLD plus one segment tree per heavy path supports vertex updates in $O(k^3{\log }^{2}n)$.

On sequences

Write $v_i=M_i\otimes v_{i-1}$ where $M_i$ depends only on $a_i$. Then $v_n=M_n\otimes \cdots \otimes M_1\otimes v_0$, and a segment tree storing products (in the right order) answers range queries and point updates.

Example: maximum weight independent set on an array with point updates. State $(f_0,f_1)$ = best with $a_i$ not taken / taken:

${\left(\begin{array}{c}{f}_0\\ f_1\end{array}\right)}_i=\left(\begin{array}{cc}0& 0\\ a_i& -\infty \end{array}\right)\otimes {\left(\begin{array}{c}{f}_0\\ f_1\end{array}\right)}_{i-1}\text{in }(\max ,+).$

Maximum subarray sum with updates is a $3\times 3$ $(\max ,+)$ matrix per element (states: not started, inside, finished). Equivalent and often simpler: store in each node the answers for every combination of boundary states (e.g. best[first taken?][last taken?]), which is the same thing as storing the matrix.

Proof: $(\max ,+)$ matrix products are associative

$(\max ,+)$ is a semiring: $\max$ is associative and commutative with identity $-\infty$, $+$ is associative with identity $0$, $+$ distributes over $\max$ ($a+\max (b,c)=\max (a+b,a+c)$), and $-\infty$ annihilates. Matrix multiplication over any semiring is associative by the usual proof (both $(AB)C$ and $A(BC)$ have entry $(i,l)$ equal to ${\max }_{j,k}(A_{ij}+B_{jk}+C_{kl})$, using distributivity and commutativity of $\max$). So a segment tree can store products of ranges.

On trees: HLD + matrices

Maximum weight independent set with vertex weight updates. With $h$ = heavy child of $v$ and $g_v$ = contribution of the light children:

$g_{v,0}={\sum }_{c\text{light}}\max (f_{c,0},f_{c,1}),g_{v,1}=a_v+{\sum }_{c\text{light}}{f}_{c,0},$

$\left(\begin{array}{c}{f}_{v,0}\\ f_{v,1}\end{array}\right)=\left(\begin{array}{cc}{g}_{v,0}& g_{v,0}\\ g_{v,1}& -\infty \end{array}\right)\otimes \left(\begin{array}{c}{f}_{h,0}\\ f_{h,1}\end{array}\right).$

The $f$ of the top of a heavy path is the product of the path’s matrices times $(0,-\infty {)}^T$ (the vector of an empty child). Updating $a_v$ changes $g_v$, hence one leaf of $v$‘s path tree; the new top value changes $g$ of the top’s parent, and so on up $O(\log n)$ light edges.

struct DynamicTreeMIS {                                    // max weight independent set, point weight updates
    static constexpr ll NEG = LLONG_MIN / 4;
    struct Mat { ll a[2][2]; };
    static Mat mul(const Mat& x, const Mat& y) {
        Mat r; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) r.a[i][j] = max({NEG, x.a[i][0] + y.a[0][j], x.a[i][1] + y.a[1][j]});
        return r;
    }
    int n; vector<vector<int>> adj; vector<ll> w;
    vector<int> par, heavy, top, pos, endPos, siz, who; vector<array<ll, 2>> g; vector<Mat> t;
    DynamicTreeMIS(const vector<vector<int>>& tree, const vector<ll>& weights) : n(sz(tree)), adj(tree), w(weights),
        par(n, -1), heavy(n, -1), top(n), pos(n), endPos(n), siz(n, 1), who(n), g(n), t(4 * max(n, 1)) {
        vector<int> order{0};
        for (int i = 0; i < sz(order); i++) for (int v : adj[order[i]]) if (v != par[order[i]]) par[v] = order[i], order.push_back(v);
        for (int i = n - 1; i > 0; i--) siz[par[order[i]]] += siz[order[i]];
        for (int u : order) for (int v : adj[u]) if (v != par[u] && (heavy[u] == -1 || siz[v] > siz[heavy[u]])) heavy[u] = v;
        int cur = 0;
        for (int u : order) {
            if (par[u] != -1 && heavy[par[u]] == u) continue;
            for (int v = u; v != -1; v = heavy[v]) top[v] = u, pos[v] = cur, who[cur++] = v;
            for (int v = u; v != -1; v = heavy[v]) endPos[v] = cur - 1;
        }
        vector<array<ll, 2>> f(n);
        for (int i = n - 1; i >= 0; i--) {
            int u = order[i]; g[u] = {0, w[u]};
            for (int v : adj[u]) if (v != par[u] && v != heavy[u]) g[u][0] += max(f[v][0], f[v][1]), g[u][1] += f[v][0];
            f[u] = g[u];
            if (int h = heavy[u]; h != -1) f[u] = {g[u][0] + max(f[h][0], f[h][1]), g[u][1] + f[h][0]};
        }
        if (n) build(1, 0, n - 1);
    }
    Mat leaf(int v) const { return Mat{{{g[v][0], g[v][0]}, {g[v][1], NEG}}}; }
    void build(int p, int l, int r) {
        if (l == r) { t[p] = leaf(who[l]); return; }
        int m = (l + r) / 2; build(2 * p, l, m); build(2 * p + 1, m + 1, r); t[p] = mul(t[2 * p], t[2 * p + 1]);
    }
    void modify(int p, int l, int r, int i) {
        if (l == r) { t[p] = leaf(who[l]); return; }
        int m = (l + r) / 2; i <= m ? modify(2 * p, l, m, i) : modify(2 * p + 1, m + 1, r, i); t[p] = mul(t[2 * p], t[2 * p + 1]);
    }
    Mat query(int p, int l, int r, int x, int y) const {
        if (x <= l && r <= y) return t[p];
        int m = (l + r) / 2;
        if (y <= m) return query(2 * p, l, m, x, y);
        if (x > m) return query(2 * p + 1, m + 1, r, x, y);
        return mul(query(2 * p, l, m, x, y), query(2 * p + 1, m + 1, r, x, y));
    }
    array<ll, 2> chain(int tp) const { Mat P = query(1, 0, n - 1, pos[tp], endPos[tp]); return {P.a[0][0], P.a[1][0]}; }
    void update(int v, ll x) {
        g[v][1] += x - w[v]; w[v] = x;
        while (v != -1) {
            int tp = top[v]; auto before = chain(tp);
            modify(1, 0, n - 1, pos[v]);
            auto after = chain(tp); int p = par[tp];
            if (p == -1) break;
            g[p][0] += max(after[0], after[1]) - max(before[0], before[1]);
            g[p][1] += after[0] - before[0];
            v = p;
        }
    }
    ll query() const { if (!n) return 0; auto f = chain(0); return max(f[0], f[1]); }
};

Proof: correctness and $O({\log }^{2}n)$ per update

For a heavy path $v_1$ (top), $v_2,\dots ,v_k$ (a leaf, whose heavy child is “empty” with $f=(0,-\infty )$), unrolling the matrix recurrence gives $f_{v_1}=M_{v_1}\otimes \cdots \otimes M_{v_k}\otimes (0,-\infty {)}^T$; multiplying by that vector takes the first column of the product, which is what chain returns. $g_v$ depends only on light children, each of which is the top of its own path, so after a path’s product changes, only the parent of its top needs its $g$ adjusted (by the difference of the contributions, which is valid because $g$ is a sum). A root-to-vertex path crosses $O(\log n)$ light edges (each light edge at least halves the subtree size), and each step costs one segment tree update and two range products, $O(\log n)$. With a single global segment tree indexed by HLD positions, the products for one path are range queries over its contiguous position range.

Variants

• Any tree DP with a constant-size state whose dependence on one child is linear in a semiring: max matching, min vertex cover, “number of ways”, path-length DPs with bounded lengths. Build $M_v$ from $g_v$ the same way.
• $O(\log n)$ per update: replace the per-path segment trees by a globally balanced binary tree (each heavy path’s binary tree is weighted by light subtree sizes), or use a link-cut tree / top tree (Link-Cut Tree, Top Trees).
• Queries on subtrees or paths instead of the whole tree: query the corresponding range of the heavy path containing the subtree root.
• Offline alternative: when updates are few and queries many, recompute; when the structure allows deletion-free processing, segment tree over time with rollback.