セグメント木: RSQ | アルゴリズムビジュアル大事典

シンボル

データ
区間の和sum
指定区間の和として返される値(※表示用のため配列にする必要はありません)res

質問に対する処理
区間和を更新します。sum[k] ← ?
指定区間の和を決定します。res ← ?
更新クエリにより更新済みの区間kの軌跡
探索区間とクエリ区間がが交わらない区間if r ≤ a or b ≤ l:
探索区間がクエリ区間に完全に含まれる区間else if a ≤ l and r ≤ b:
探索区間がクエリ区間とクエリ区間外を含む区間else:

アニメーション

質問に対する処理
セグメント木: RSQ | 質問に対する処理