GDCass1ni's blog

Prefix Sum — A high-level magical algorithm
By GDCass1ni, history, 6 months ago, In English

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
  • Vote: I like it
  • -42
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it -20 Vote: I do not like it

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.

→ Reply
»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply