Dynamic Sum Arrays
We have an array of 50000 integers. We are also given 50000 commands, either of type Q or type C. Q-type commands, or queries, given x, are to return the sum of the first x numbers in the array. C-type commands increments the value of a given index, x, in the array by 1. What is the most optimal approach?
Approach 1: Plain Array (Straightforward)
We store the 50000 integers in an array. For every query, we sum up the first x numbers. For a command, we increment the value at x. Make: O(n) Query: O(n) Command: O(1)
Approach 2: Dumb Prefix Summing
For every C-type command, including initialization, we add 1 to every value beyond x. To query, we simply access index x. Make: O(n^2) Query: O(1) Command: O(n)
Approach 3: Recorded Prefix Summing
In initialization, we keep track of the current cum and add the value to the current sum and then copy the value to the index. Everything else is same as approach 2. Make:O(n) Query: O(1) Command: O(n)
We need something better!
Approach 4: Choppy Prefix Sums
Instead of numbering every number, we only number specific details and benchmarks occurring every N numbers.So, in a command, we only increment every number between x and the next benchmark. After that, we only increment benchmarks. To query, we add the number at index x with the last benchmark. Query: O(1) Command: O(n/x+x)