DSU on tree

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /dsu-on-tree#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /dsu-on-tree#noredirect を利用してください。
name
DSU on tree
short description
DSU on tree とは、それぞれの頂点 $x$ に可換 monoid $(M, +, 0)$ の要素の重み $a_x$ のついた木 $T$ のそれぞれの部分木について、その部分木内の重みの総和を全体で $O(n \log n)$ で求めるアルゴリズムである。ただし、その計算の過程において、monoid 演算 $+$ がある要素 $A \in M$ と頂点 $x$ に対し $A + a_x$ という形でしか出現しないという特徴がある。