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.
Input
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).
Output
For each query, output the answer to that query on its own line in the order the queries were made.
Example
Input: 3
1 4 1
3
1 1
1 2
0 2 Output: 4
5
6
hide comments
|
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 :) |
|
shanto09:
2020-06-19 17:59:08
Simple prefix sum problem. As the time constraint is very high brute force would work. |
|
rohitkk074:
2020-06-06 19:00:19
use prefix sum |
|
lazy_zeus:
2020-04-28 10:27:54
It has a 7s limit, obviously, brute force would get accepted. |
|
karthikn_2099:
2019-08-02 14:54:35
even brute force approach is getting accepted
|
|
veerendrasd_9:
2019-05-25 07:47:22
Use segment trees, for any range queries.
|
|
tanu_1603070:
2018-05-19 07:42:28
Dataset is very weak :/
|
| Added by: | Joshua Kirstein |
| Date: | 2014-10-27 |
| Time limit: | 7s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | Hi Mom! |
RSS