Today I'm going to introduce an amazing algorithm — Prefix Sum.
First, let's consider below problem.
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.
implementation
Why is this blog downvoted? It helps me a lot and I will implement it by myself later.
Is there a link to this problem? I want to submit it to check if it is correct.
This is the same problem but with $$$1 \le n,q \le 2 \cdot 10^5$$$ : https://cses.fi/problemset/task/1648
Hi,
Your solution shouldn't work because $$$O(nq)$$$ is too slow (it is equal to $$$10^{12}$$$ for the worst testcase) I recommand you to learn segment trees and/or fenwick trees and with that, you could solve this problem in $$$O(qlog n)$$$ very easily (you can find it on this link)
Sorry for my bad english
It is correct.
You are out.
$$$\mathcal O(nq)(n,q \le 10^6)$$$ can easily get AC now.
How?
I am out。
That's true.