このページは下書きです。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$ という形でしか出現しないという特徴がある。