Search⌘ K
Home
Courses
Competitive Programming in C++: The Keys to Success

Solved Problem - Subarray Sum

Explore how to efficiently compute the sum of elements in any subarray using prefix sums. This lesson guides you through building and using a prefix sum array to answer multiple sum queries in optimal time, enhancing your skills in solving array problems for programming contests.

We'll cover the following...

Problem statement

Given an array, AA, of NN integers, answer QQ queries of the type (l,r)(l, r) - sum of the elements in the subarray A[l...r]A[l...r]. Print the sum for each query.

Input format

The first line contains two space-separated integers NN and QQ (1≤N,Q≤106)(1 \leq N,Q \leq 10^6).

The second line contains NN integers representing the array ...