Competitive Programming C++ Cheatsheet

This comprehensive document organizes all major algorithms, data structures, and templates for
competitive programming in C++. Each section contains ready-to-use code snippets for fast
recall and implementation.

1. Basic Templates
Template 1

#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
using ll=int64_t;

signed main() {
IOS int _t;cin>>_t;
while (_t--) {

}
}

Template 2

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//using ll=int64_t;
#define int long long

void solve() {

#undef int
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int _t;cin>>_t;while (_t--)
solve();
}
2. Mathematics
Binary Exponentiation (Recursive)

ll binexp(ll a, ll b, ll p_=1e9+7) { //log(b)

if (!b) return 1;
if (b%2) return a*binexp(a, b-1, p_)%p_;
ll _=binexp(a,b>>1LL,p_);
return _*_%p_;
}

Binary Exponentiation (Iterative)

long long binexp(long long a, long long b, long long m) {

a %= m;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}

Prime Factorization

unordered_map<ll,ll> get_divisors(ll n) { //O(sqrt(n))

unordered_map<ll,ll> ans;
ll _=sqrt(n);
for (ll i=2;i<=_;i++)
while (!(n%i)) {
ans[i]++;
n/=i;
}
if (n>1) ans[n]++;
return ans;
}

Euclidean GCD

ll gcd(ll a, ll b) { //O(log(min(a,b)))
if (!a) return b;
if (a>b) swap(a,b);
return gcd(b%a, a);
}

Sieve of Eratosthenes
 vector<bool> get_prime_sieve(ll n) {//O(nloglogn)
vector<bool> is_prime(n+1, true);
is_prime[^0]=is_prime[^1]=false;
for (ll i=2;i<=n;i++)
if (is_prime[i])
for (ll j=i*i; j<=n; j+=i)
is_prime[j]=false;
return is_prime;
}

Primes up to n

vector<ll> get_primes_upto(ll n) {//O(nloglogn)

vector<ll> vc;
vector<bool> is_prime(n+1, true);
is_prime[^0]=is_prime[^1]=false;
for (ll i=2;i<=n;i++)
if (is_prime[i]) {
vc.push_back(i);
for (ll j=i*i; j<=n; j+=i)
is_prime[j]=false;
}
return vc;
}

Segmented Sieve

vector<bool> get_segmented_sieve(ll a, ll b) {//O((b-a)loglogb)

vector<bool> is_prime(b-a+1, true);
for (ll i:get_primes_upto(sqrt(b))) {
for (ll j=max(i*i, (a+i-1)/i*i); j<=b;j+=i)
is_prime[j-a]=false;
}
return is_prime;
}

Fast Factorization (Smallest Prime Array)

vector<int> sp;
void gen_sp_array(ll n) { //O(nloglogn)
sp.resize(n);
for (int i=2;i<n;i++)
sp[i]=i;
for (int i=2;i<n;i++)
if (sp[i]==i)
for (ll j=1LL*2*i; j<=sp.size();j+=i)
sp[j]=i;
}

unordered_map<ll,ll> get_divisors_fast(ll a) { //O(loga)

unordered_map<ll,ll> factors;
while (a>1) {
 factors[sp[a]]++;
a /= sp[a];
}
return factors;
}

Binomial Coefficient (Mod M)

vector<ll> fact, inv_fact;

void build_C(int N=100000, ll M=1e9+7) { //O(n)
fact.assign(N+1,0); inv_fact.assign(N+1,0);
fact[^0]=fact[^1]=1;
for (int i=2;i<=N;i++)
fact[i]=(fact[i-1]*i)%M;
inv_fact[N]=binexp(fact[N], M-2);
for (int i=N; i>=1;i--)
inv_fact[i-1]=(i*inv_fact[i])%M;
}

ll C(ll n, ll r, ll M=1e9+7) { //O(1)

if (r>n) return 0;
return fact[n]*inv_fact[n-r]%M*inv_fact[r]%M;
}

Power of Prime in n!

ll power_of_prime(ll n, ll p) { //O(logn)
ll ans=0;
while (n) ans+=(n/=p);
return ans;
}

3. Bit Manipulation
Basic Bitwise Functions

#define setbit(n,i) ((n)|(1LL<<(i))) //Add element to the set

#define unset(n,i) ((n)&(~(1LL<<(i)))) //Remove element
#define check(n,i) (((n)>>(i))&1LL) //Is present?
#define flip(n,i) ((n)^(1LL<<(i)))
#define flipall(n,i) ((n)^(~0LL))
//__builtinpopcount(x) -> Set bits
//__builtinctz(x) -> Trailing zeros
//__builtinclz(x) -> Leading zeros

#define remove_last_setbit(n) ((n)&(n-1))

#define get_last_setbit(n) ((n)&(~(n-1)))

Bit Trie
struct node {
int child[^2];
int cnt=0;
node () {
memset(child,-1,sizeof(child));
}
};

#define LN 32
struct bittrie {
vector<node> nodes;
bittrie() {
node root;
nodes.push_back(root);
}

void insert(ll x) {
int cur_node=0;
for (int i=LN-1;i>=0;--i) {
int v=(x>>i)&1;
if (nodes[cur_node].child[v]==-1) {
node new_node;
nodes.push_back(new_node);
nodes[cur_node].child[v]=nodes.size()-1;
}
nodes[cur_node].cnt++;
cur_node=nodes[cur_node].child[v];
}
nodes[cur_node].cnt++;
}

void erase(ll x) {
int cur_node=0;
for (int i=LN-1;i>=0;--i) {
int v=(x>>i)&1;
nodes[cur_node].cnt--;
cur_node=nodes[cur_node].child[v];
}
nodes[cur_node].cnt--;
}

ll query(ll x) {
ll y=0;
int cur_node=0;
for (int i=LN-1;i>=0;--i) {
int v=(x>>i)&1;
if (nodes[cur_node].child[!v]!=-1 && nodes[nodes[cur_node].child[!v]].cnt>0)
if ((!v)==1) y|=(1ll<<i);
cur_node=nodes[cur_node].child[!v];
} else {
if (v==1) y|=(1ll<<i);
cur_node=nodes[cur_node].child[v];
}
}
return x^y;
 }
};

4. Data Structures
Monotone Deque

template <class T>

struct monotone_deque {
deque<T> dq;
void insert(T k) {
while (!dq.empty() && dq.back()>k)
dq.pop_back();
dq.push_back(k);
}
void erase(T k) {
if (dq.front() == k)
dq.pop_front();
}
int min() {
if (!dq.empty())
return dq.front();
else return INT_MIN;
}
};

Indexed Set (PBDS)

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update>
indexed_set;
//order_of_key: Number of items strictly smaller than k
//find_by_order: Iterator to the ith largest element

Next Greatest Element (Monotone Stack)

stack<int> st_index;
int ngi[n];
for (int i = n-1; i>=0; i--) {
while (!st_index.empty() && arr[st_index.top()] <= arr[i])
st_index.pop();
if (st_index.empty())
ngi[i] = n;
else ngi[i] = st_index.top();
st_index.push(i);
}
5. Searching Algorithms
Binary Search (Basic)

ll lo=0, hi=_upper_limit_, ans=_default_value_;

while (hi>=lo) {
ll mid=(lo+hi)/2;
if (check(arr, mid)) {
ans=mid;
hi=mid-1;
} else lo=mid+1;
}

Ternary Search

ll lo = 0, hi = a/b;
while (hi-lo>3) {
ll mid1 = (lo*2+hi)/2;
ll mid2 = (lo+hi*2)/2;
if (func(mid1)>func(mid2)) //For Minima
lo= mid1;
else hi = mid2;
}
ld ans=a;
for (ll i=lo; i<=hi; i++)
ans = min(ans, func(i));

Binary Search (Real Domain)

ld lo=0.0, hi=__upper_limit__, ans=0.0;

while (abs(lo-hi)>1e-9) {
ld mid=(lo+hi)/2.0;
if (check(mid)) {
ans=mid;
lo=mid;
}else hi=mid;
}
cout << fixed<<setprecision(6)<<ans<< endl;

Two Pointer (from Start)

int head=-1, tail=0;

__ds__
int ans=0;
while (tail<n) {
while (head+1<n && __condition_for_head_to_move_forward__) {
head++;
__do_something_on_ds__
}
ans=__update_ans__;

if (head>=tail) {
 __do_reset_something_on_ds__
tail++;
} else {
tail++;
head=tail-1;
}
}

Two Pointers (Both Sides)

int i=0, k=n-1;

while (i<j && j<k) {
if (arr[i]+arr[j]+arr[k]==T) {
int itemp=i;
int ktemp=k;
while (itemp<j && arr[itemp]==arr[i])
itemp++;
while (ktemp>k && arr[ktemp]==arr[k])
ktemp--;
cnt+=(itemp-i)*(k-ktemp);
i=itemp;
k=ktemp;
} else if (arr[i]+arr[j]+arr[k]<T)
i++;
else k--;
}

6. Recursion, D&C, Backtracking, and Miscellaneous

LLCM Framework (Backtracking)

/*
The LCCM framework for backtracking.
Choose the DS used to store the current configuration.
O(ch1*ch2......*chn*(Base recursion complexity + sum(all checks)))
L - Level
C - Choice
C - Check function (For checking the validity of the choice)
M - Move (Change config., Level up and recurse, Restore config.)

void rec(T lvl)

__breaking_condition__ //Base case where answer is updated
for (all choices)
check(choice)
move(lvl+1)
*/

Merge Sort (DnC)

vector<int> mergesort(vector<int> &arr) { //O(nlogn)

int n=arr.size();
 if (n==1) return arr;
vector<int> ans;ans.resize(n);
vector<int> p[^2];
for (int i=0;i<n;i++) p[i&1].push_back(arr[i]);
vector<int> s1=mergesort(p[^0]), s2=mergesort(p[^1]);
int i=0,j=0,k=0;
while (i<s1.size() && j<s2.size()) {
if (s1[i]<=s2[j])
ans[k++]=s1[i++];
else ans[k++]=s2[j++];
}
while (i<s1.size()) ans[k++]=s1[i++];
while (j<s2.size()) ans[k++]=s2[j++];
return ans;
}

Meet in the Middle

(No direct code; used for subset/4sum problems. Split set, enumerate all sums of subsets,
combine using binary search or hashing.)

7. Graph Algorithms
Adjacency List Input

vector<vector<int>> g;
vector<bool> vis;
int n,m; cin>>n>>m;
g.resize(n+1);
for (int i=0;i<m;i++) {
int a, b;
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a); //If undirected
}
vis.assign(n+1,0);

DFS Outline

void dfs(node x) {
// Mark node x as visited.
// Do some operation on the node like coloring, component id...
for (node neighbour:adj_list[x])
if (Not marked visited)
dfs(neighbour);
}

BFS Template (Unweighted)

using state=pair<int,int>;
vector<vector<int>> dis;
vector<vector<bool>> vis;
 vector<state> get_neighbours(state node) {
//Fill in
}

void bfs(state st_node) {

queue<state> q;
dis[st_node.F][st_node.S]=0;
q.push(st_node);
while (!q.empty()) {
auto tp=q.front();
q.pop();
if (vis[tp.F][tp.S])continue;
vis[tp.F][tp.S]=1;
for (auto &k:get_neighbours(tp)) {
if (dis[k.F][k.S]>dis[tp.F][tp.S]+1) {
dis[k.F][k.S]=dis[tp.F][tp.S]+1;
q.push(k);
}
}
}
}

Cycle Detection (DFS Coloring)

vector<int> col;
bool is_cycle=0;

void dfs(int node, int p) {

col[node]=2; //mark it visited
for (auto v:g[node]) {
//if (v==p) continue; //necessary for undirected
if (col[v]==1) {
dfs(v, node);
} else if (col[v]==2) {
is_cycle=true;
}
}
col[node]=3;
}

Topological Sort (Kahn's Algorithm)

vector<int> indeg;
vector<int> topo;
void kahn() {
queue<int> q;
for (int i=1;i<=n;i++)
if (indeg[i]==0)
q.push(i);
while (!q.empty()) {
int cur=q.front();
q.pop();
topo.push_back(cur);
 for (auto v:g[cur]) {
indeg[v]--;
if (indeg[v]==0)q.push(v);
}
}
}

0/1 BFS

vector<int> dist;
vector<bool> vis;

void BFS01(int sc) {

deque<int> q;
dist[sc]=0;
q.push_back(sc);

while (!q.empty()) {
int cur=q.front();
q.pop_front();
if (vis[cur]) continue;
vis[cur]=1;

for (auto v:g[cur]) {

if (dist[v.F]>dist[cur]+v.S) {
dist[v.F]=dist[cur]+v.S;
if (v.S) q.push_back(v.F);
else q.push_front(v.F);
}
}
}
}

Dijkstra's Algorithm

class prioritize {
public: bool operator() (ii &p1, ii &p2) {
return p1.S>p2.S;
}
};

vector<lli> dist;
vector<bool> vis;

void dikstra(int sc) {

dist.assign(n+1, 1e18);
vis.assign(n+1,0);
dist[sc]=0;
priority_queue<pii, vector<pii>, prioritize> q;
q.push(MP(sc,0));
while (!q.empty()) {
pii fs=q.top(); q.pop();
if (vis[fs.F]) continue;
vis[fs.F]=1;
 for (auto v:g[fs.F]) {
int neigh=v.F, wt=v.S;
if (dist[neigh]>dist[fs.F]+wt) {
dist[neigh]=dist[fs.F]+wt;
q.push({neigh, dist[neigh]});
}
}
}
}

Bellman-Ford

vector<pair<ii,int>> g;
vector<ll> dist;
vector<bool> vis;
bool neg_cyc=false;
for (int i=0;i<n;i++) {
for (auto e:g) {
if (dist[e.F.S]>dist[e.F.F]+e.S) {
dist[e.F.S]=dist[e.F.F]+e.S;
if (i==n-1) neg_cyc=true;
}
}
}

Floyd-Warshall

int n,m;
int dist[^404][^404];
int par[^404][^404];

void print_path(int i, int j) {

if (i!=j) print_path(i, par[i][j]);
cout << j << endl;
}

signed main() {
IOS cin>>n>>m;
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
if (i!=j)dist[i][j]=1e9;
for (int i=0;i<m;i++) {
int a,b,c; cin>>a>>b>>c;
dist[a][b]=min(dist[a][b],c);
}
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
par[i][j]=i;
}
}
for (int k=0;k<n;k++) {
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
if (dist[i][j]>dist[i][k]+dist[k][j]) {
 dist[i][j]=dist[i][k]+dist[k][j];
par[i][j]=par[k][j];
}
}
}
}
}

Articulation Points/Bridges (Tarjan's Algorithm)

vector<bool> vis;
vector<int> tin,tlow;
unordered_set<int> art_pt;
int timer;

void dfs(int i, int p=-1) {

vis[i]=1;
tin[i]=tlow[i]=timer++;
int children=0;
for (auto v:g[i]) {
if (v==p) continue;
if (vis[v])
tlow[i]=min(tlow[i], tin[v]);
else {
dfs(v, i);
tlow[i]=min(tlow[i], tlow[v]);
if (tlow[v]>=tin[i] && p!=-1)
art_pt.insert(v);
children++;
}
}
if (p==-1 && children>1)
art_pt.insert(i);
}

Union Find (Disjoint Set)

class UnionFind {
private:
int n,set_size, *parent, *rank;
public:
UnionFind(){}
UnionFind(int a) {
n=set_size=a;
parent=new int[n+1];
rank=new int[n+1];
for (int i=1;i<=n;i++) parent[i]=i, rank[i]=1;
}
int find(int x) {
if (x!=parent[x]) return parent[x]=find(parent[x]);
return x;
}
bool merge(int x, int y) {
int xroot=find(x), yroot=find(y);
 if (xroot!=yroot) {
if (rank[xroot]>=rank[yroot]) {
parent[yroot]=xroot;
rank[xroot]+=rank[yroot];
} else {
parent[xroot]=yroot;
rank[yroot]+=rank[xroot];
}
set_size--;
return 1;
}
return 0;
}
void reset() {
set_size=n;
for (int i=1;i<=n;i++) parent[i]=i, rank[i]=1;
}
};

Kruskal's Algorithm

UnionFind uf(n);
vector<pair<int,ii>> edge_list;
int a,b,c;
for (int i=0;i<m;i++) {
cin>>a>>b>>c;
edge_list.push_back({c,{a,b}});
}
sort(edge_list.begin(), edge_list.end());

int mst_cost=0;
for (auto v:edge_list) {
int x=v.S.F, y=v.S.S;
if (uf.find(x)!=uf.find(y)) {
mst_cost+=v.first;
uf.merge(x,y);
}
}
cout << mst_cost << endl;

Kosaraju’s Algorithm (SCC)

vector<vector<int>> g, grev;
vector<int> vis(100100,0);
vector<int> tout_order;
void dfs1(int x) {
vis[x]=1;
for (auto v:g[x]) {
if(!vis[v])
dfs1(v);
}
tout_order.push_back(x);
}
int cur_scc=0;
 int scc_num[^100100];
void dfs2(int x) {
scc_num[x]=cur_scc;
vis[x]=1;
for (auto v:grev[x])
if (!vis[v])
dfs2(v);
}
vector<vector<int>> condensed_graph;

void condense() {
for (int i=1;i<=n;i++)
if (!vis[i])
dfs1(i);
reverse(tout_order.begin(), tout_order.end());
vis.assign(n+1,0);
for (auto x:tout_order)
if (!vis[x]) {
cur_scc++;
dfs2(x);
}
condensed_graph.resize(cur_scc+1);
for (int i=1;i<=n;i++) {
for (auto v:g[i]) {
if (scc_num[i]!=scc_num[v])
condensed_graph[scc_num[i]].push_back(scc_num[v]);
}
}
}

8. Trees
Tree Implementation

vector<vector<int>> g;
vector<int> dep, par, subtree_sz, numChild;
vector<bool> is_leaf;

void dfs(int node, int parent, int depth) {

dep[node]=depth;
par[node]=parent;
subtree_sz[node]=1;
numChild[node]=0;
for (auto v:g[node]) {
if (v!=parent) {
numChild[node]++;
dfs(v, node, depth+1);
subtree_sz[node]+=subtree_sz[v];
}
}
if (!numChild[node])
is_leaf[node]=1;
}
Tree Diameter

void dotree(int node, int parent, int depth, vector<vector<int>>&g,vector<int>&dep,vector

dep[node]=depth;
par[node]=parent;
for (auto v:g[node]) if (v!=parent)
dotree(v, node, depth+1,g,dep,par);
}

//Diameter
vector<int> dep, par; dep.resize(n); par.resize(n);
dotree(0,-1,0,g,dep,par);
int max_dep_node=0;
for (int i=0;i<n;i++) if (dep[i]>dep[max_dep_node])max_dep_node=i;
dotree(max_dep_node,-1,0,g,dep,par);
max_dep_node=0;
for (int i=0;i<n;i++) if (dep[i]>dep[max_dep_node])max_dep_node=i;
int dia=dep[max_dep_node];

//Centres
vector<int> ans;
int node_=max_dep_node;
for (int i=0;i<dia/2;i++)node_=par[node_];
ans.push_back(node_);
if (dia&1) ans.push_back(par[node_]);

Tree Centroid

int get_centroid(int node, int parent) {

for (auto v:g[node])
if (v!=parent)
if (subtree_sz[v]>n/2)
return get_centroid(v, node);
return node;
}

Lowest Common Ancestor (LCA)

int n;
vector<int> g[^100100];
int depth[^100100], parent[^100100][^20];

void dfs(int node, int par, int dep) {

parent[node][^0]=par;
depth[node]=dep;
for (int i=1;i<20;i++) {
parent[node][i]=parent[parent[node][i-1]][i-1];
}
for (auto v:g[node]) {
if (v!=par)
dfs(v,node,dep+1);
}
}
 int lca(int u, int v) {
if (depth[u]<depth[v]) swap(u,v);
for (int i=19;i>=0;i--)
if ((depth[u]-depth[v])&(1<<i))
u=parent[u][i];
if (u==v) return u;
for (int i=19;i>=0;i--) {
if (parent[v][i]!=parent[u][i]) {
v=parent[v][i];
u=parent[u][i];
}
}
return parent[u][^0];
}

9. Strings & Hashing

Trie (Basic)

struct node {
int child[^26];
node(){
memset(child,-1,sizeof(child));
}
};

struct trie {
vector<node> nodes;
trie() {
node rootnode;
nodes.push_back(rootnode);
}
void insert(string s) {
int cur_node_idx=0;
for (int i=0;i<s.size();i++) {
if (nodes[cur_node_idx].child[s[i]-'a']==-1) {
node new_node;
nodes.push_back(new_node);
nodes[cur_node_idx].child[s[i]-'a']=nodes.size()-1;
}
cur_node_idx=nodes[cur_node_idx].child[s[i]-'a'];
}
}
int get_node_count() {
return nodes.size();
}
};

KMP Algorithm
 string s;cin>>s;
int n=s.length();
int kmp[n+1];
int i=0,j=-1; kmp[^0]=-1;
while (i<n) {
while (j!=-1 && s[i]!=s[j]) j=kmp[j];
j++;i++;
kmp[i]=j;
}

Z Algorithm

vector<int> z_function(string s) {
int n = s.size();
vector<int> z(n);
int l = 0, r = 0;
for(int i = 1; i < n; i++) {
if(i < r) {
z[i] = min(r - i, z[i - l]);
}
while(i + z[i] < n && s[z[i]] == s[i + z[i]]) {
z[i]++;
}
if(i + z[i] > r) {
l = i;
r = i + z[i];
}
}
return z;
}

Manacher Algorithm

struct manacher {
vector<int> p;
void run_manacher(string s) {
int n=s.length();
p.assign(n,1);
int l=1,r=1;
for (int i=1;i<n;i++) {
p[i]=max(0,min(r-i,p[l+r-i]));
while (i+p[i]<n && i-p[i]>=0 && s[i+p[i]]==s[i-p[i]]) {
p[i]++;
}
if (i+p[i]>r) {
l=i-p[i];
r=i+p[i];
}
}
}
void build(string s) {
string t;
for (auto v:s) t+=string("#")+v;
 run_manacher(t+"#");
}
int getLongest(int cen, bool odd) {
int pos=2*cen+1+(!odd);
return p[pos]-1;
}
bool isPalindrome(int l, int r) {
if ((r-l+1)<=getLongest((l+r)/2,l%2==r%2))
return 1;
return 0;
}
};

Rolling Hash

ll quickHash(string s, ll p=31, ll mod=999999929) {

ll ans=s[^0]-'a'+1;
for (int i=1;i<s.length();i++)
ans=(ans*p+(s[i]-'a'+1))%mod;
return ans;
}
struct hasher {
int sz; ll mod,p;
vector<ll> fHash, rHash;
vector<ll> pk;
void init(string &s, ll _p=31, ll _mod=999999929) {
mod=_mod; p=_p;
sz=s.length();
fHash.resize(sz); pk.resize(sz);
fHash[^0]=s[^0];
pk[^0]=1;
for (int i=1;i<s.length();i++) {
fHash[i]=(fHash[i-1]*p+(s[i]-'a'+1))%mod;
pk[i]=pk[i-1]*p%mod;
}
rHash.resize(sz);
rHash[sz-1]=s.back()+1;
for (int i = sz-2; i >= 0; i--)
rHash[i] = (rHash[i + 1]*p + (s[i]-'a'+1))%mod;
}
ll getfHash(int l, int r) {
if (l==0) return fHash[r];
return ((fHash[r]-fHash[l-1]*pk[r-l+1]%mod)%mod+mod)%mod;
}
ll getrHash(int l, int r) {
if (r==sz-1) return rHash[l];
return ((rHash[l]-rHash[r+1]*pk[r-l+1]%mod)%mod+mod)%mod;
}
};
struct dhasher {
hasher h1,h2;
void init(string &s, ll p1=31, ll p2=37, ll mod1=999999929, ll mod2=999999937) {
h1.init(s,p1,mod1);
h2.init(s,p2,mod2);
}
 pair<int,int> getfHash(int l, int r) {
return {h1.getfHash(l,r),h2.getfHash(l,r)};
}
};

10. Dynamic Programming

DP Basic Structure

int dp[...][...][...];
__DS__ rec(__form_state__, __aggregates__) {
//pruning

//base_case

//cache check

//transition

//save and return

}

Knapsack Merge Format

int n,k;
vector<int> g[^101];
int arr[^101];
int sz[^101];
int dp[^101][^2][^101];
void dfs(int nn, int pp) {
for (int i=0;i<=k;i++) {
dp[nn][^1][i]=(i==1?arr[nn]:-1e9);
dp[nn][^0][i]=(i==0?0:-1e9);
}
sz[nn]=1;
for (auto v:g[nn]) if (v!=pp) {
dfs(v,nn);
for (int a=sz[nn];a>=0;a--) for (int b=sz[v];b>=0;b--) {
dp[nn][^0][a+b]=max(dp[nn][^0][a+b],dp[nn][^0][a]+max(dp[v][^0][b],dp[v][^1][
dp[nn][^1][a+b]=max(dp[nn][^1][a+b],dp[nn][^1][a]+dp[v][^0][b]);
}
sz[nn]+=sz[v];
}
}

SOS DP

const int N=20;

void forward1(int *dp) {
for (int i=0;i<N;i++) for (int m=0;m<(1<<N);m++) if ((m>>i)&1)
dp[m]+=dp[m^(1<<i)];
 }
void backward1(int *dp) {
for (int i=0;i<N;i++) for (int m=(1<<N)-1;m>=0;m--) if ((m>>i)&1)
dp[m]-=dp[m^(1<<i)];
}
void forward2(int *dp) {
for (int i=0;i<N;i++) for (int m=(1<<N)-1;m>=0;m--) if ((m>>i)&1)
dp[m^(1<<i)]+=dp[m];
}
void backward2(int *dp) {
for (int i=0;i<N;i++) for (int m=0;m<(1<<N);m++) if ((m>>i)&1)
dp[m^(1<<i)]-=dp[m];
}

11. Segment Trees

Segment Tree (Basic)

int n,q;
int arr[^200100];
int t[^800400]; //4*n

void build(int idx, int l, int r) {

if (l==r) { t[idx]=arr[l]; return; }
int mid=(l+r)/2;
build(idx*2,l,mid);
build(idx*2+1,mid+1,r);
t[idx]=t[2*idx]+t[2*idx+1];
}

void update(int idx, int l, int r, int pos, int val) {

if (pos<l||pos>r) return;
if (l==r) {
t[idx]=val;
return;
}
int mid=(l+r)/2;
update(idx*2,l,mid,pos,val);
update(idx*2+1,mid+1,r,pos,val);
t[idx]=t[2*idx]+t[2*idx+1];
}

int query(int idx, int l, int r, int lq, int rq) {

if (l>rq||lq>r) return 0;
if (lq<=l&&r<=rq) return t[idx];
int mid=(l+r)/2;
return query(idx*2,l,mid,lq,rq)+query(idx*2+1,mid+1,r,lq,rq);
}

Segment Tree with Lazy Propagation

 struct node {
int sum,maxr,lazy;
node(){
sum=maxr=lazy=0;
}
};

node merge(node a, node b) {

node temp;
temp.sum=a.sum+b.sum;
temp.maxr=max(a.maxr,b.maxr);
return temp;
}

int n,q;
int arr[^200100];
node t[^800400];

void push(int idx, int l, int r) {

if (t[idx].lazy) {
t[idx].sum=t[idx].lazy*(r-l+1);
t[idx].maxr=t[idx].lazy;
if (l!=r) {
t[idx<<1].lazy=t[idx].lazy;
t[idx<<1|1].lazy=t[idx].lazy;
}
t[idx].lazy=0;
}
}

void update(int idx, int l, int r, int lq, int rq, int v) {
push(idx,l,r);
if (lq>r||l>rq) return;
if (lq<=l&&r<=rq) {
t[idx].lazy=v;
push(idx,l,r);
return;
}
int mid=(l+r)>>1;
update(idx<<1,l,mid,lq,rq,v);
update(idx<<1|1,mid+1,r,lq,rq,v);
t[idx]=merge(t[idx<<1],t[idx<<1|1]);
}

node query(int idx, int l, int r, int lq, int rq) {

push(idx,l,r);
if (l>rq||lq>r) return node();
if (lq<=l&&r<=rq) return t[idx];
int mid=(l+r)>>1;
return merge(query(idx<<1,l,mid,lq,rq),query(idx<<1|1,mid+1,r,lq,rq));
}

This document is ready for memorization and quick reference. Practice writing and using
these templates regularly to master competitive programming.
⁂