セグメント木は位置のブロックごとに要約を保存します:葉は1つの値を持ち、各親は2つの子を結合します。和(単位元は0)、最小値(単位元は無限大)、最大値、gcd(単位元は0)など、結合的で単位元を持つ演算ならどれでも使えます。すると範囲の問い合わせはO(log n)個のブロックを結合し、1点の更新は葉から根までの1本の経路を再計算します。
ボトムアップ版は数行で書けます:葉はnから2n - 1、親i = combine(2i, 2i + 1)です。演算を引き算で取り消せない(最小値、最大値、gcd)場合や、値がx以上になる最初の位置のように木の中を探索する必要がある場合など、フェニック木では足りないときに使ってください。
更新が範囲全体に及ぶときは、遅延伝播を加えてください:更新に覆われたノードは変更を記録し、子が必要になったときにだけ子へ渡します。面接では、まず結合関数とその単位元を述べ、次に更新とクエリのコストを述べてください。