Competitive Programming Notes

Template​ 1
Basic Data Types​ 1
Built-in Functions​ 1
Data Structures​ 4
Algorithms​ 6
Array Sorting​ 6
Binary Search​ 6
Kadane's Algorithm​ 7
Divide and Conquer algorithms​ 8
Graph Theory​ 9
Fenwick Tree​ 9
Segment Tree​ 9
Adjacency Matrix​ 12
DFS​ 13
BFS​ 14
Dijkstra​ 16
Dynamic Programming​ 17
Prefix Sum Array​ 17
Iterators, Recursion​ 18
Range Query​ 20
Queries on static arrays​ 20
Sum queries​ 20
Minimum queries​ 21
Time Complexity​ 21

Template & Basic Data Type

Built-in Functions
C++ Built-in Functions Cheat Sheet
1. Basic Utility Functions
●​ std::max(a, b), std::min(a, b)
○​ Returns the maximum/minimum of two values.
○​ Reference
●​ std::swap(a, b)
○​ Swaps values of a and b.
○​ Reference
2. Sorting & Searching
●​ std::sort(begin, end)
○​ Sorts elements in ascending order (default).
○​ Reference
●​ std::binary_search(begin, end, value)
○​ Checks if value exists in a sorted range.
○​ Reference
●​ std::lower_bound(begin, end, value)
○​ Finds the first position where value can be inserted without changing order.
○​ Reference
●​ std::upper_bound(begin, end, value)

1 of 21
 ○​ Finds the first position strictly greater than value.
○​ Reference
3. Numeric & Math Functions
●​ std::gcd(a, b), std::lcm(a, b)
○​ Computes GCD and LCM.
○​ Reference
●​ std::pow(base, exp), std::sqrt(x), std::ceil(x), std::floor(x),
std::round(x)
○​ Exponentiation, square root, rounding functions.
4. Data Structures & Algorithms
●​ std::priority_queue<T>
○​ Implements a max-heap (default) or min-heap.
○​ Reference
●​ std::unordered_map<Key, Value>, std::unordered_set<T>
○​ Fast O(1) average-time complexity lookup.
○​ Reference
5. Graph Algorithms
●​ std::queue<T> (for BFS), std::stack<T> (for DFS)
○​ BFS and DFS traversal utilities.
6. Time Measurement
●​ std::chrono::high_resolution_clock::now()
○​ Measures execution time.
○​ Reference
7. Threading & Concurrency
●​ std::thread t(function_name)
○​ Creates a new thread for parallel execution.
○​ Reference
8. String Manipulation
●​ std::stoi(str), std::stoll(str), std::stod(str)
○​ Convert string to integer, long long, or double.
●​ std::to_string(x)
○​ Converts number x to a string.
9. Bit Manipulation
●​ __builtin_popcount(x), __builtin_ctz(x), __builtin_clz(x)
○​ Counts set bits, trailing zeroes, leading zeroes (for GCC/Clang).
Extra Knowledge: Iterators in C++
Iterators are like pointers that traverse STL containers like vector, set, map.
●​ Forward Iterator → Read/write, single-pass (vector, list)
●​ Bidirectional Iterator → Move forward & backward (map, set)
●​ Random Access Iterator → Supports indexing (vector, deque)

Data Structures
In C++, there are generally 3 kinds of STL (Standard Library) containers:
●​ Sequence Containers: data is sequentially ordered
●​ Associative Containers: elements are stored in a sorted order (order does not depend on
when the element is inserted)
●​ Unordered associative containers: position of elements does not matter
There are also container adaptors which are not full container classes, but classes that provide a
specific interface relying on an object of one of the container classes to handle the elements.​
More reading: https://cplusplus.com/reference/stl/

Basic Data Structures

// Include the vector library
#include <vector>
// Include the list library
#include <list>
// Include the set library

2 of 21
#include <set>
// Include the map library
#include <map>
// Include the stack library
#include <stack>
// Include the queue library
#include <queue>

Array int x[5]; //declaring an array

●​ Fixed sized sequential collection of x[0] = 3; //set the first item in the array to 3
same data type elements sort(x, x+5); //sorts x in ascending order
reverse(x, x+5); //reverses x

Multidimensional Array string letters[2][4] = {

{ "A", "B", "C", "D" },
{ "E", "F", "G", "H" }
};

Vector vector<int> x; //declaring a vector

●​ Sequence containers representing x.push_back(5); //insert 5 from the back
arrays that can change in size x.pop_back(); //remove the last item
●​ Automatically changes size when x.insert(x.begin()+3, 2); //insert 2 at the 4th
element is inserted or deleted position
●​ Occupies more memory than arrays x.erase(x.begin()+1); //remove the 2nd item

Stack stack<int> x; //declaring a stack

●​ Container adaptors with LIFO (Last In x.push(5); //insert 5 at the top
First Out) operation x.pop(); //remove topmost item
●​ Only topmost element can be queried x.size(); //return size of x
or removed x.top() //return topmost item
●​ Insertion only from the top

Queue queue<int> x; //declaring a queue

●​ Container adaptors with FIFO (First In x.push(5); //insert 5 at the back
First Out) operation x.pop(); //remove frontmost item
●​ Only first and last elements can be x.size(); //return size of x
queried x.front(); //return frontmost item
●​ Insertion only from the top, removal x.back(); //return last item
only from the back

Priority queue priority_queue<int> x; //declaring a priority queue

●​ Special type of queue where each x.push(7)
element is associated with a priority x.push(5)
value cout << x.top(); //7
●​ Only maximum or minimum elements
can be queried
●​ Smaller constant factors than a
multiset
●​ Good for when only minimum or
maximum elements need to be
queried

Deque (double-ended queue) pronounced deque<int> x; //declaring a deque

dee-queue or deck x.push_back(5); //insert 5 from the back
●​ Sequence containers that can be x.pop_back(); //remove the last item
efficiently manipulated at both ends x.push_front(7) //insert 7 from the front
x.pop_front() //remove the first item

3 of 21
 ●​ Similar to vector, but more efficient in x.insert(x.begin()+3, 2); //insert 2 at the 4th
insertion and deletion of elements position
x.erase(x.begin()+1); //remove the 2nd item
x.front(); //returns frontmost item
x.back(); //returns last item
x.size(); //return size of x

Set set<int> x; //declaring a set

●​ Associative containers that store x.insert(5)
unqiue elements in a specific order x.insert(6)
●​ Note that elements are distinct x.insert(7)
x.find(5) //returns an iterator that points to 5 in x
(-1 in 5 is not in x)
x.lower_bound(5) //returns an iterator to the
smallest item in x that is >=5
x.upper_bound(7) //returns an iterator to the
largest item in x that is >=7

Unordered set unordered_set<int> x; //declaring a unordered set

●​ Essentially a set that is unordered
(also implemented differently from a
set)

Multiset multiset<int> x; //declaring a multiset

●​ Essentially a set that can have
several copies of the same value

Unordered multiset unordered_multiset<int> x; //declaring an

●​ Essentially a multiset that is unordered multiset
unordered

map<string, int> x; //declaring a map map<string, int> x; //declaring a map

//insert //insert
x["word"] = 4; x["word"] = 4;
x["notword"] = 5; x["notword"] = 5;
x["awesome"] = 1; x["awesome"] = 1;

Unordered Map unordered_map<string, int> x; //declaring an

unordered map

Very Hard Data Structure: Policy Based Data Structure

●​ Somewhat similar to sets, but with extra, more powerful operations
●​ Not part of the C++ standard library (but still supported by the g++ compiler)

//include these headers to use policy-based structures

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

//namespace
using namespace __gnu_pbds;

//defining a data structure indexed_set (for int values)

typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;

//defining a data structure multi_indexed_set (for int values)

4 of 21
 typedef tree<int,null_type,less_equal<int>,rb_tree_tag, tree_order_statistics_node_update>
multi_indexed_set;

indexed_set s;
s.insert(2);
s.insert(5);
s.insert(7);
s.insert(9);

auto x = s.find_by_order(2); //returns an iterator to the element at a given position

cout << *x; //7

cout << s.order_of_key(7); //returns the position of a given element

//these functions work in log(n) time!

Algorithms
Array Sorting

1. std::sort() – Fastest and Most Used

vector<int> arr = {5, 2, 9, 1, 5, 6};
sort(arr.begin(), arr.end()); //
Ascending order
sort(arr.rbegin(), arr.rend()); //
Descending order

✅ Time Complexity: O(N log N)​

✅ Use Case: General sorting (default is ascending)
2. std::stable_sort() – Maintains Order of
Equal Elements
stable_sort(arr.begin(), arr.end());

✅ Time Complexity: O(N log² N) worst-case​

✅ Use Case: When element order matters
3. Counting Sort – Best for Small Integers

For small integers (0 ≤ arr[i] ≤ 10⁶), Counting Sort runs in O(N + K).

vector<int> count(1000001, 0);

for (int x : arr) count[x]++;
vector<int> sorted;
for (int i = 0; i < count.size(); i++)
while (count[i]--) sorted.push_back(i);

✅ Time Complexity: O(N + K) (K = range of numbers)​

✅ Use Case: When sorting integers in a small range

5 of 21
Which One to Use?std::sort() → Best for general use (default choice);
std::stable_sort() → Use when stability matters; Counting Sort → Use for sorting small
integers fast; For NOI, std::sort() is almost always the best choice! 🚀
Binary Search
Binary Search is a searching algorithm that allows for finding the index of an element in an array in
O(logn) time.​
How it works:
●​ sort the array arr in ascending order
●​ set a left index l to be the first element of the array, set a right index r to be the last element of
the array
●​ set the middle index mid to be the average of these 2 indexes
○​ if arr[mid]==target element, then the value has been found
○​ if arr[mid]<target element, then set r to be mid−1
○​ if arr[mid]>target element, then set l to be mid+1
●​ repeat previous step until value has been found or r<l
Implementation (copied from cp-algorithms.com):

//a is the sorted array

int l = -1, r = n;
while(r - l > 1) {
int m = (l + r) / 2;
if(k < a[m]) {
r = m; // a[l] <= k < a[m] <= a[r]
} else {
l = m; // a[l] <= a[m] <= k < a[r]
}

int binarySearch(int arr[], int l, int r, int x)

{
if (r >= l) {
int mid = l + (r - l) / 2;

// If the element is present at the middle

// itself
if (arr[mid] == x)
return mid;

// If element is smaller than mid, then

// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);

// Else the element can only be present

// in right subarray
return binarySearch(arr, mid + 1, r, x);
}

// We reach here when element is not

// present in array
return -1;
}

6 of 21
Usage:
●​ used to find
○​ lower bound: index of the first element that is >= a given value
○​ upper bound: index of the first element that is > a given value
●​ Binary Search on The Answer (BSTA)
○​ binary search can be used to find the answer x of a function f(x) such that f(x)=true
○​ only works on monotonic functions (functions that are always non-decreasing/always
non-increasing)
○​ more info here

Kadane's Algorithm
Kadane's Algorithm solves the largest contiguous subarray problem: given an array of size N, find the
sum of the contiguous subarray within the array with the largest sum.​
How it works:
●​ go through the array and accumulate:
○​ the current partial sum in some variable s
○​ the maximum sum of contiguous subarray found so far in some variable m
●​ if s<0 at any point, we assign s=0
●​ if s>m at any point, we assign m=s
Implementation (copied from cp-algorithms.com):

int ans = a[0], ans_l = 0, ans_r = 0;

int sum = 0, minus_pos = -1;

for (int r = 0; r < n; ++r) {

sum += a[r];
if (sum > ans) {
ans = sum;
ans_l = minus_pos + 1;
ans_r = r;
}
if (sum < 0) {
sum = 0;
minus_pos = r;
}
}

Divide and Conquer algorithms

Divide and Conquer is a technique used to solve large problems by breaking the problem into smaller
subproblems, solving these subproblems individually and combining them to get the desired output.
Therefore, this technique is divided into 3 parts:
1.​ Divide: divide problem into smaller subproblems
2.​ Conquer: solve sub-problems by calling recursively until solved
3.​ Combine: combine the sub-problems to get the solution
Contrary to popular belief, Binary Search is NOT an example of Divide and Conquer. Binary Search
compares the middle value of the input element with that of the middle of the subarray. If the value is
not the same, the algorithm recurs for the corresponding side of the sorted subarray. Since there is
only 1 subproblem in each step, it is a Decrease and Conquer algorithm. Divide and Conquer
algorithms must have 2 or more subproblems in each step.
Divide and Conquer to find the maximum
int max(int arr[], int l, int r) {
// base case
if(l == r) {
return arr[l];
}

else {

7 of 21
 int m = (l+r)/2;
int lm = max(arr, l, m);
int rm = max(arr, m+1 , r);

return (lm > rm) ? lm : rm;

}
}

Examples of algorithms that use Divide and Conquer

1.​ Quicksort​
The algorithm picks a pivot element and rearranges the array elements so that all elements
smaller than the picked pivot element move to the left side of the pivot, and all greater
elements move to the right side. Finally, the algorithm recursively sorts the subarrays on the
left and right of the pivot element.
2.​ Merge Sort​
The algorithm divides the array into two halves, recursively sorts them, and finally merges the
two sorted halves.
​

References
●​ Divide and Conquer Algorithm: Introduction (geeksforgeeks)
●​ Divide and Conquer Algorithm (programiz)

Graph Theory

Fenwick Tree
●​ calculates the sum of elements over a given range in an array in O(logn) time
●​ updates the value of an element of in an array in O(logn) time
●​ requires O(n) memory

Segment Tree

✅ 🚀
A Fenwick Tree efficiently computes prefix sums and supports point updates in O(log N) time.
Use Cases: Dynamic prefix sums, inversion count, range queries.

Fenwick Tree
// C++ code to demonstrate operations of Binary Index Tree
#include <iostream>

using namespace std;

/* ​ n --> No. of elements present in input array.

BITree[0..n] --> Array that represents Binary Indexed Tree.
arr[0..n-1] --> Input array for which prefix sum is evaluated. */

// Returns sum of arr[0..index]. This function assumes

// that the array is preprocessed and partial sums of
// array elements are stored in BITree[].
int getSum(int BITree[], int index)
{
int sum = 0; // Initialize result

8 of 21
 // index in BITree[] is 1 more than the index in arr[]
index = index + 1;

// Traverse ancestors of BITree[index]

while (index>0)
{
// Add current element of BITree to sum
sum += BITree[index];

// Move index to parent node in getSum View

index -= index & (-index);
}
return sum;
}

// Updates a node in Binary Index Tree (BITree) at given index

// in BITree. The given value 'val' is added to BITree[i] and
// all of its ancestors in tree.
void updateBIT(int BITree[], int n, int index, int val)
{
// index in BITree[] is 1 more than the index in arr[]
index = index + 1;

// Traverse all ancestors and add 'val'

while (index <= n)
{
// Add 'val' to current node of BI Tree
BITree[index] += val;

// Update index to that of parent in update View

index += index & (-index);
}
}

// Constructs and returns a Binary Indexed Tree for given

// array of size n.
int *constructBITree(int arr[], int n)
{
// Create and initialize BITree[] as 0
int *BITree = new int[n+1];
for (int i=1; i<=n; i++)
BITree[i] = 0;

// Store the actual values in BITree[] using update()

for (int i=0; i<n; i++)
updateBIT(BITree, n, i, arr[i]);

// Uncomment below lines to see contents of BITree[]

//for (int i=1; i<=n; i++)
// ​ cout << BITree[i] << " ";

return BITree;

9 of 21
}

// Driver program to test above functions

int main()
{
int freq[] = {2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(freq)/sizeof(freq[0]);
int *BITree = constructBITree(freq, n);
cout << "Sum of elements in arr[0..5] is "
<< getSum(BITree, 5);

// Let use test the update operation

freq[3] += 6;
updateBIT(BITree, n, 3, 6); //Update BIT for above change in arr[]

cout << "\nSum of elements in arr[0..5] after update is "

<< getSum(BITree, 5);

return 0;
}
Segment Tree
#include <bits/stdc++.h>
using namespace std;

// limit for array size

const int N = 100000;

int n; // array size

// Max size of tree

int tree[2 * N];

// function to build the tree

void build( int arr[])
{
// insert leaf nodes in tree
for (int i=0; i<n; i++)
tree[n+i] = arr[i];

// build the tree by calculating parents

for (int i = n - 1; i > 0; --i)
tree[i] = tree[i<<1] + tree[i<<1 | 1];
}

// function to update a tree node

void updateTreeNode(int p, int value)
{
// set value at position p
tree[p+n] = value;
p = p+n;

10 of 21
 // move upward and update parents
for (int i=p; i > 1; i >>= 1)
tree[i>>1] = tree[i] + tree[i^1];
}

// function to get sum on interval [l, r)

int query(int l, int r)
{
int res = 0;

// loop to find the sum in the range

for (l += n, r += n; l < r; l >>= 1, r >>= 1)
{
if (l&1)
res += tree[l++];

if (r&1)
res += tree[--r];
}

return res;
}

// driver program to test the above function

int main()
{
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};

// n is global
n = sizeof(a)/sizeof(a[0]);

// build tree
build(a);

// print the sum in range(1,2) index-based

cout << query(1, 3)<<endl;

// modify element at 2nd index

updateTreeNode(2, 1);

// print the sum in range(1,2) index-based

cout << query(1, 3)<<endl;

return 0;
}

Adjacency Matrix
int adjMat[n][n];
memset(adjMat, -1, sizeof adjMat);
cin >> u >> v >> w; // 0, 1, 6
adjMat[u][v] = w;

11 of 21
Adjacency List
0: (1, 6), (2, 3)
1: (3, 1)
2: (1, 2)
3: -
4: (3, 4)
typedef pair<int, int> ii;
vector<ii> adjList[n];
cin >> u >> v >> w; // 0, 1, 6
adjList[u].push_back(ii(v, w));

Edge list
[(0, 1, 6),
(0, 2, 3),
(1, 3, 1),
(2, 1, 2),
(4, 3, 4)]
typedef tuple<int, int, int> iii;
vector<iii> edgeList;
cin >> u >> v >> w; // 0, 1, 6
edgeList.push_back(iii(u, v, w));

Single-Source Shortest Path (SSSP)

Unweighted: BFS; Weighted +ve: Dijkstra’s; Weighted -ve: Bellman-Ford; Small graph: Floyd-Warshall

Single-Source Single-Destination Shortest Path (SSSDSP)

Same as SSSP, except query dist[t] only

Single-Destination Shortest Path (SDSP)

Reverse direction of all edges, then treat as SSSP

Multi-Sources Shortest Path (MSSP)

Initialize all dist[s] = 0, then treat as SSSP

SSSDSP Reconstruction
Keep track of the parent u of each vertex v (p[v] = u), then recursively print from p[t] to p[s]

DFS
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;

typedef vector<ii> vii;
typedef vector<int> vi;

enum { UNVISITED = -1, VISITED = -2 }; //basic flags

//these variables have to be global to be easily accessible by our

recursion (other ways exist)
vector<vii> AL;
vi dfs_num;

void dfs(int u) { //normal usage

12 of 21
 printf(" %d", u); //this vertex is visited
dfs_num[u] = VISITED; //mark u as visited
for (auto &[v, w] : AL[u]) //C++17 style, w ignored
if (dfs_num[v] == UNVISITED) //to avoid cycle
dfs(v); //recursively visits v
}

int main() {
/*
//Undirected Graph in Figure 4.1
9
1 1 0
3 0 0 2 0 3 0
2 1 0 3 0
3 1 0 2 0 4 0
1 3 0
0
2 7 0 8 0
1 6 0
1 6 0
*/

freopen("dfs_cc_in.txt", "r", stdin);

int V; scanf("%d", &V);
AL.assign(V, vii());

for (int u = 0; u < V; ++u) {

int k; scanf("%d", &k);
while (k--) {
int v, w; scanf("%d %d", &v, &w);
AL[u].emplace_back(v, w);
}
}

printf("Standard DFS Demo (the input graph must be UNDIRECTED)\n");

dfs_num.assign(V, UNVISITED);
int numCC = 0;
for (int u = 0; u < V; ++u) // for each u in [0..V-1]
if (dfs_num[u] == UNVISITED) // if that u is unvisited
printf("CC %d:", ++numCC), dfs(u), printf("\n"); // 3 lines
here!
printf("There are %d connected components\n", numCC);

return 0;
}

BFS
#include <bits/stdc++.h>
using namespace std;

13 of 21
typedef pair<int, int> ii; // In this chapter, we will frequently use these
typedef vector<ii> vii; // three data type shortcuts. They may look cryptic
typedef vector<int> vi; // but shortcuts are useful in competitive
programming
const int INF = 1e9; // INF = 1B, not 2^31-1 to avoid overflow

vi p; ​ // addition:parent vector
void printPath(int u) { ​ // extract info from vi p
if (p[u] == -1) { printf("%d", u); return; }
printPath(p[u]); ​ // output format: s -> ...
-> t
printf(" %d", u);
}

int main() {
/*
// Graph in Figure 4.3, format: list of unweighted edges
// This example shows another form of reading graph input
13 16
0 1​1 2​ 2 3 0 4 1 5 2 6​ 3 7 5 6
4 8​8 9​ 5 10 6 11 7 12 9 10 10 11 11 12
*/

freopen("bfs_in.txt", "r", stdin);

int V, E; scanf("%d %d", &V, &E);
vector<vii> AL(V, vii());
for (int i = 0; i < E; ++i) {
​ int a, b; scanf("%d %d", &a, &b);
​ AL[a].emplace_back(b, 0);
​ AL[b].emplace_back(a, 0);
}

// as an example, we start from this source, see Figure 4.3

int s = 5;

// BFS routine inside int main() -- we do not use recursion

vi dist(V, INF); dist[s] = 0; ​ // INF = 1e9 here
queue<int> q; q.push(s);
p.assign(V, -1); ​ // p is global

int layer = -1; ​ // for output printing

bool isBipartite = true; ​ // additional feature
while (!q.empty()) {
​ int u = q.front(); q.pop();
​ if (dist[u] != layer) printf("\nLayer %d: ", dist[u]);
​ layer = dist[u];
​ printf("visit %d, ", u);
​ for (auto &[v, w] : AL[u]) { ​
// C++17 style, w ignored
​ ​ if (dist[v] == INF) {
​ ​ ​ dist[v] = dist[u]+1; ​ // dist[v] !=
INF now

14 of 21
 ​ ​ ​ p[v] = u; ​ // parent of v
is u
​ ​ ​ q.push(v); ​ // for next
iteration
​ ​ }
​ ​ else if ((dist[v]%2) == (dist[u]%2)) ​ // same parity
​ ​ isBipartite = false;
​ }
}

printf("\nShortest path: ");

printPath(7), printf("\n");
printf("isBipartite? %d\n", isBipartite);
return 0;
}

Dijkstra
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;

typedef vector<int> vi;
typedef vector<ii> vii;
const int INF = 1e9; // INF = 1B, not 2^31-1 to avoid overflow

int main() {
/*
// Graph in Figure 4.17
5 7 0
0 1 2
0 2 6
0 3 7
1 3 3
1 4 6
2 4 1
3 4 5
*/
freopen("dijkstra_in.txt", "r", stdin);
int V, E, s; scanf("%d %d %d", &V, &E, &s);
vector<vii> AL(V, vii());
while (E--) {
​ int u, v, w; scanf("%d %d %d", &u, &v, &w);
​ AL[u].emplace_back(v, w); ​// directed graph
}
vi dist(V, INF); dist[s] = 0; ​ // INF = 1e9 here

// Original Dijkstra's algorithm

/*
set<ii> pq; ​ // balanced BST version
for (int u = 0; u < V; ++u) ​ // dist[u] = INF
​ pq.insert({dist[u], u}); ​// but dist[s] = 0

15 of 21
 // sort the pairs by non-decreasing distance from s
while (!pq.empty()) { ​ // main loop
​ auto [d, u] = *pq.begin(); ​// shortest unvisited u
​ pq.erase(pq.begin());
​ for (auto &[v, w] : AL[u]) { ​// all edges from u
​ if (dist[u]+w >= dist[v]) continue; ​ // not improving, skip
​ pq.erase(pq.find({dist[v], v})); ​ // erase old pair
​ dist[v] = dist[u]+w; ​ // relax operation
​ pq.insert({dist[v], v}); ​ // enqueue better pair
​ }
}
*/
// (Modified) Dijkstra's algorithm
priority_queue<ii, vector<ii>, greater<ii>> pq; pq.push({0, s});
// sort the pairs by non-decreasing distance from s
while (!pq.empty()) { ​ // main loop
​ auto [d, u] = pq.top(); pq.pop(); ​// shortest unvisited u
​ if (d > dist[u]) continue; ​// a very important check
​ for (auto &[v, w] : AL[u]) { ​// all edges from u
​ if (dist[u]+w >= dist[v]) continue; ​ // not improving, skip
​ dist[v] = dist[u]+w; ​ // relax operation
​ pq.push({dist[v], v}); ​ // enqueue better pair
​ }
}

for (int u = 0; u < V; ++u)

​ printf("SSSP(%d, %d) = %d\n", s, u, dist[u]);

return 0;
}

Dynamic Programming
Dynamic Programming is an algorithmic paradigm that splits a complex problem into subproblems
and stores answers of these subproblems to avoid computing these results again. It is an optimization
over plain recursion, which reduces time complexity from exponential to polynomial. However, it
increases space complexity (not a huge concern in competitive programming).
Dynamic programming is used to efficiently solve problems with 2 main properties: overlapping
subproblems and optimal substructure. Overlapping Subproblems Property Dynamic Programming
combines solutions to sub-problems. When the same subproblems are repeatedly needed, dynamic
programming is used.
Prefix Sum Array
2D Prefix Sum array
The general formula:
psa[i][j] = psa[i-1][j] + psa[i][j-1] -
psa[i-1][j-1] + a[i][j]

16 of 21
// C++ Program to find prefix sum of 2d array
#include <bits/stdc++.h>
using namespace std;

#define R 4
#define C 5

// calculating new array

void prefixSum2D(int a[][C])
{
int psa[R][C];
psa[0][0] = a[0][0];

// Filling first row and first column

for (int i = 1; i < C; i++)
psa[0][i] = psa[0][i - 1] + a[0][i];
for (int i = 1; i < R; i++)
psa[i][0] = psa[i - 1][0] + a[i][0];

// updating the values in the cells

// as per the general formula
for (int i = 1; i < R; i++) {
for (int j = 1; j < C; j++)

// values in the cells of new

// array are updated
psa[i][j] = psa[i - 1][j] + psa[i][j - 1]
- psa[i - 1][j - 1] + a[i][j];
}

// displaying the values of the new array

for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++)
cout << psa[i][j] << " ";
cout << "\n";
}
}

// driver code
int main()
{
int a[R][C] = { { 1, 1, 1, 1, 1 },

17 of 21
 { 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1 } };

prefixSum2D(a);

return 0;
}

Iterators, Recursion
Iterators act like pointers and are used to traverse elements in STL containers like vector, set,
map, etc.
Types of Iterators
1.​ Input Iterator → Read-only, single-pass (e.g., cin)
2.​ Output Iterator → Write-only, single-pass (e.g., cout)
3.​ Forward Iterator → Read/write, multiple passes (e.g., forward_list)
4.​ Bidirectional Iterator → Read/write, move forward & backward (e.g., list, map)
5.​ Random Access Iterator → Supports indexing (e.g., vector, deque)
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
std::vector<int> vec = {10, 20, 30, 40, 50};

std::vector<int>::iterator it = std::find(vec.begin(), vec.end(), 30);

if (it != vec.end())
std::cout << "Found at position: " << (it - vec.begin()) << "\n";
}

Recursion is a method of solving problems by solving smaller instances of itself. Essentially, recursion
is a process where a function calls itself.​
A recursive function solves problems by calling a copy of itself and solving smaller subproblems of the
original problems. Many more recursive calls can be generated if needed. Recursion performs the
same operations multiple times with different inputs. It makes the input smaller each time to make the
problem smaller and easier.​
The Base condition/case of recursion is the stopping condition of recursion, to stop the growth of the
number of recursive calls. This helps prevent an infinite loop.

Why use recursion?

●​ Significantly reduces the length of code and make it easier to read. It provides elegance in
complex data structures and algorithms.
●​ Reduces the need for complex loops and auxiliary data structures. Similar to the first point,
simplifies your code.
●​ Reduces time complexity with memoization. Memoization is an optimization technique used to
speed up programs by returning the cached result when the same input occurs again.
●​ Works well with trees and graphs. Important in graph theory.

Issues with using recursion

●​ Can incur CPU overhead and cause slowness.
●​ Can lead to out-of-memory errors and stack overflow exceptions.
●​ Can cause unnecessarily complex code if poorly constructed. Make sure recursion is used
well and not unnecessarily.

18 of 21
Call Stack​
When a recursive function is called, it goes on top of the "call stack". This "call stack" uses a Last In
First Out (LIFO) method like a regular stack. This means that functions called last will be executed
first.​
In recursion, function calls are nested until the base case is reached. Without the base case, there
would be infinite nested function calls.​
The depth of recursion is the maximum degree of nesting the function calls over the course of
computation. The programming environment has to maintain a pushdown stack of size proportional to
the depth of the recursion. For huge problems, the space needed for this stack might prevent the use
of plain recursion.

Recursion VS Iteration
Recursion Iteration

1 Terminates when base case becomes true Terminates when loop condition
becomes false

2 Uses functions Uses loops

3 Each recursive call needs additional memory in Each iteration does not use extra
the stack memory memory

4 Smaller code size, more elegant Larger code size

Applications of recursion​
Recursion is obviously very important and has widespread use. In competitive programming,
recursion is used for:
1.​ Divide and conquer
2.​ Dynamic programming
3.​ Graphs
4.​ Trees

Examples​
1. Factorial function:
int factorial(int n) {
// base case
if(n==0) {
return 1;
}

return n*factorial(n-1);
}

2. Fibonacci Sequence function:

int fibonacci(int n) {
// base case
if(n==1 || n==2) {
return 1;
}

else return fibonacci(n-1)+fibonacci(n-2);

}

3. Euclidean Algorithm function:

int euclid(int a, int b) {
// base case
if(b == 0) {
return a;

19 of 21
 }

else return euclid(b, a % b);

}
​
References
●​ Recursion (geeksforgeeks)
●​ Recursion in Programming (course by freeCodeCamp.org on youtube)
●​ How Recursion Works (freecodecamp)
●​ Memoization (wikipedia)

Range Query​
A query over a certain range in a set of elements. This includes range sum queries (calculating the
sum of values) and range minimum queries (finding the minimum value).​
Range queries can be static, where the set of elements is not changes in between queries, or
dynamic, where the set of elements can be updated.
Queries on static arrays
When the set of elements is static and not updated, preprocessing will be suffice to efficiently
answering range queries.

Sum queries
A range sum query denotes the sum of array values in a specific range (e.g. 0-5).
Sum queries can be easily processed using a prefix sum array, where every value is equal to the sum
of values in the original array up to the corresponding position.
A prefix sum array can be constructed in O(n) time, using the formula: psa[i]=psa[i−1]+a[i] This allows
for calculation of any range sum query in O(1) time. For example, when the queried range is (a, b):
sum=psa[b]−psa[a−1]
We can even calculate a two-dimensional range sum using a 2D prefix sum array (a.k.a. prefix sum
matrix): psa[i][j]=psa[i−1][j]+psa[i][j−1]−psa[i−1][j−1]+a[i][j]

Minimum queries
A range minimum query in the form of l, r denotes the minimum element in an array between l and r
inclusive.​
There are many ways to efficiently solve range minimum queries, some of which even work when the
array is dynamic (modifications to the array between queries).

Sparse Table​
A Sparse Table is a data structure that allows answering range queries in mostly O(log(n)) time, or
O(1) time for range minimum queries. However, this data structure can only be used on
static/immutable arrays.
How it works:​
Any non-negative number can be uniquely represented as a sum of decreasing powers of two e.g.
13=8+4+1. Similarly, any interval can be uniquely represented as a union of intervals with lengths that
are decreasing powers of 2.​
The main idea behind Sparse Tables is to precompute all answers for range queries with power of two
length. Afterwards a different range query can be answered by splitting the range into ranges with
power of two lengths, then combining precomputed answers to receive a complete answer.
Implementation:​
We create a table lookup such that lookup[i][j] contains the minimum of range i to i+2j−1.​
Here is a C++ implementation:
#define MAX 5000 //arbitrary number
int lookup[MAX][MAX];

void init(int arr[], int n) {

for(int i=0;i<n;i++) {
lookup[i][0] = arr[i];
}

for(int j=1;(1<<j)<=n;j++) {
for(int i=0;i+(1 << j)-1<n;i++) {

20 of 21
 lookup[i][j] = min(lookup[i][j-1], lookup[i+(1<<(j-1))][j-1]);
}
}
}

int query(int l, int r) {

int len = r-l+1, j=0;
while((l<<(j+1))<=len) {
j++;
}
return min(lookup[l][j], lookup[r-(1<<j)+1][j]);
}

Time Complexity

Grading System: WA: wrong answer; RTE: run-time error; MLE: memory limit exceeded; TLE: time
limit exceeded; AC: all correct
Big O rule of thumb​
Big O notation is used as an abstraction of time complexity.​
In general, the value inside the O() should
be >= time limit * 1000000
●​ 10^6: O(N)/O(log N)/O(1)
●​ 10^5: O(N log N)
●​ 10^3: O(N^2)
●​ 10^2: O(N^3)
●​ 10: O(N!)/O(2^N)
Fast IO for C++
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);

Things that are handwritten:

Greedy
Prefix Sum (not the 2d one)
vector<int> ps(n);
ps[0] = a[0];
for(int i=1;i<n;i++) {
​ ps[i] = ps[i-1] + a[i];
}

Fibonacci

int fib = 1;
int prev = 0;
for(int i=0;i<n;i++) {
​ fib += prev;
​ prev = fib - prev;
}

// recursive!
int fibonacci(int n) {
// base case
if(n==1 || n==2) {
return 1;
}
else return fibonacci(n-1)+fibonacci(n-2);
}

21 of 21
Repeated elements, so store the repeated ones: Memoisation Top down
vector<int> memo(n, -1);
memo[1] = 1; memo[2] = 1;
int fibonacci(int n) {
​ if(memo[n] != -1) {
return memo[n];
}
memo[n] = fibonacci(n-1)+fibonacci(n-2);
return memo[n];
}

Top up:
vector<int> memo(n, -1);
memo[1] = 1; memo[2] = 1;
for(int i=3;i<=n;i++) {
memo[i] = (memo[i-2] + memo[i-1]);
}

More DP

22 of 21