Add, Assign, Range Sum — Solution & Editorial

Back to the Problem

A Fenwick tree gives O(log N) point add and prefix sum; assignment is an add of (new − old). Range sum = prefix(r) − prefix(l−1).

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

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