Dynamic Range Sum — Solution & Editorial

Back to the Problem

A segment tree (or Fenwick tree where the aggregate is invertible) supports both operations in O(log N). Point-assign updates the leaf and re-aggregates up the path.

Complexity: O((N + Q) log N)

Watch out: Sums reach 10¹¹ — 64-bit.