ツリー上の差分#
説明#
差分配列（前方和ではない）をツリー上に置き、特定のノードの重みがそのノード自身とすべての子ノードの差分の合計に等しくなるようにします。（意味不明）
差分配列の役割は、区間の変更の時間計算量を低くすることであり、ツリーに適用すると、このような状況に応じて使用できます：
点の差分#
A—B の単純なパス上のすべてのノードの重みを 1 増加させます。
このパスを A から L（A と B の LCA）および B から L の 2 つのチェーンに分解できます。
A と B のマークを 1 増加させると、A から L および B から L に対応する値が統計時に 1 ずつ増加し、L の値は合計で 2 増加するため、L のマークを 1 減少させます。L の親ノードは、差分配列の区間を変更する際のその区間の後の点のように、そのマークを 1 減少させます。
辺の差分#
辺の重みを下の点に変換します。
したがって、今回 L 点のマークは動かせず、区間が 1 増加するたびに L 点のマークは 2 減少させる必要があります。