CSUMQ - Cumulative Sum Query

no tags 

William Macfarlane wants to look at an array.

You are given a list of numbers and queries. Each query is specified by two numbers 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 <= 10,000). The next Q lines each contain two numbers i and 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
1 1
1 2
0 2

hide comments
mojoalpha: 2022-01-14 18:47:07

Using a segment tree could be a great choice too, in case you need more than one solution for this question

sourav_halder: 2021-06-16 16:47:34

use partial sum

eager_to_code: 2021-06-16 16:14:44

is there any discussion tab?

shreyasz_07: 2021-06-13 14:52:53

use kruskal algorithm

sandy5823: 2021-05-30 00:20:28


sugam10: 2021-04-28 06:57:37

use prefix sum

Last edit: 2021-04-28 06:58:19
mazharul_sub: 2021-03-22 20:53:53

i am a dumb

linhthebest: 2021-02-23 03:09:18

I´m a faggot.

Last edit: 2021-02-23 10:52:10
nitish_verma26: 2021-02-01 14:18:29

Sparse table is best suited for these type of questions where original array is not changing. One should go for this.

adikrmishra_1: 2020-06-29 19:36:40

simple prefix sum question with some if else conditions :)

Added by:Joshua Kirstein
Time limit:7s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Hi Mom!