Today I'm going to introduce an amazing algorithm — Prefix Sum.

First, let's consider below problem.

You could solve it by brute-force, but it was too slow.

Let's consider Prefix Sum — let $$$s_i = \sum \limits_{j=1}^i a_j$$$, we could answer queries in $$$\mathcal O(1)$$$, the sum of $$$[l,r]$$$ is $$$s_r - s_{l-1}$$$.

Then let's learn how to perform changes. When $$$a_x \gets y$$$, $$$s_x \sim s_n$$$ will change. We could just change it one by one and perform a change in $$$\mathcal O(n)$$$.

Time complexity: $$$\mathcal O(nq)$$$, which is fast enough to pass the tests.