CSUMQ - Cumulative Sum Query
William Macfarlane wants to look at an array.
You are given a list of N numbers and Q queries. Each query is specified by two numbers i and j; the answer to each query is the sum of every number between the range [i, j] (inclusive).
Note: the query ranges are specified using 0-based indexing.
The first line contains N, the number of integers in our list (N <= 100,000). The next line holds N numbers that are guaranteed to fit inside an integer. Following the list is a number Q (Q <= 10,000). The next Q lines each contain two numbers i and j which specify a query you must answer (0 <= i, j <= N-1).
For each query, output the answer to that query on its own line in the order the queries were made.
1 4 1
Using a segment tree could be a great choice too, in case you need more than one solution for this question
use partial sum
is there any discussion tab?
use kruskal algorithm
use prefix sum
i am a dumb
I´m a faggot.Last edit: 2021-02-23 10:52:10
Sparse table is best suited for these type of questions where original array is not changing. One should go for this.
simple prefix sum question with some if else conditions :)