Gain insights into competitive programming, explore C++ skills with theory, code samples, practice problems, and master faster implementation for contests like ACM ICPC, Google CodeJam, and HackerCup.

Competitive programming can be a great way to build out your programming skills, get on any major company’s radar, and earn a little extra cash along the way.

In this course, you will learn to prepare for competitive programming contests like ACM ICPC, Google CodeJam, Facebook HackerCup, and many more.

Each topic is broken down with a healthy mix of theory, code samples, step-by-step solved sample problems, illustrations, useful practice problems, and tips and tricks for faster implementation.

You will need some solid C++ foundations coming into this course, but by the end it, you will be confident enough in your C++ skills to take home the win.

Competitive Programming in C++: The Keys to Success

# Problem statement
Given an array, $A$, of $N$ integers, answer $Q$ queries of the type $(l, r)$ - sum of the elements in the subarray $A[l...r]$. Print the sum for each query.

**Input format**

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

The second line contains $N$ integers representing the array $A[]$ $(1 \leq A[i] \leq 10^6)$. 

The next $Q$ lines each contain a pair of integers $l$ and $r$.

**Output format**

Print $Q$ integers and answer to the queries.

---

# Sample

**Input**
```
5 3
1 2 4 8 16
1 5
2 3
3 5
```
**Output**
```
31 6 28
```
---

# Brute force
The brute force method would be to loop over the subarray in the query and sum all the elements.

I am skipping the code for this solution because it is trivial.


The time for each query would be $O(N)$, the total complexity of the solution would be $O(Q*N)$. This means it is not good enough for the given constraints.

# Optimization
First, let’s discuss what the prefix sum array is.

The prefix sum array $sum[]$ of an array $A[]$ is defined as

$sum[i] = \sum_{k=1}^{i} A[k]$

or, $i$th element of $sum[]$ is sum of first $i$ elements of $A[]$

We can use the prefix sum array to find the sum of a subarray in $O(1)$ time.

$sum[i...j] = A[i] + A[i+1] + ... + A[j]$

$=$ $(A[1] + A[2] + ... +A[j]) - (A[1] + A[2] + ... +A[i-1])$

$=$ $sum[j] - sum[i-1]$

From preprocessing to computing the $sum[]$ array takes $O(N)$ time. Each query is just $O(1)$.

So the total time complexity is $O(N + Q)$.

See the below illustration for a better understanding.


In this lesson, we'll see an effective way to compute sum of an subarray.

Introduction

Complexity Analysis

Number Theory

Arrays and Vectors

Sieve of Eratosthenes

Strings

Sorting

Linked List

Stack

Queue

Binary Tree

2 Pointers

Heap

Binary Search Tree

Balanced Binary Search Tree

Course Conclusion

Solved Problem - Subarray Sum

Problem statement