Add, Assign, Range Sum — Solution & Editorial | Jobs at Avian IT

Hiring process8 levels

1 IQ Test
2 Additional Online Test (If Required)
3 Office Interview with Hiring Manager
4 Unpaid Test Task (Motivation Check)
5 Paid Test Task and Follow-Up Interview
6 Iterative Paid Test Tasks
7 Office Verification
8 Final Interview with the Founder

Problems > Add, Assign, Range Sum > Editorial

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.