Prefix Sum — A high-level magical algorithm

Revision en1, by GDCass1ni, 2024-01-22 18:24:19

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English GDCass1ni 2024-01-22 18:24:19 964 Initial revision (published)