Bellman Ford

Binary Search

Increasing Array lower_bound() returns value that is greater than or equal to x; upper_bound() returns value strictly greater than x; Decreasing array: lower_bound() returns value that is less than or equal to x; upper_bound() retruns value that is strictly less than x;

DFS Order

A very useful technique.It basically has 2 arrays one is Intime and the other is outTime. inTime says when it enters a recursion stack and outTime says when it exits the recursion stack. It is useful to check if a node v is present in the subtree of node u. If inTime[u]<inTime[v] and outTime[u]> outTime[v]. It can also be useful in counting number of nodes that belong to a particular tree at a particular height.

General facts

Online vs Offline Online algorithm means getting output after processing at ith element for eg: median of a stream of elements, Whereas in case of online means using all n elements to arrive at an output.

LCA

LCA Using Binary Lifting k=0 means the parent node Create a table P[K][N] -> N is number of nodes 2^k<=N So k<=logN Hence Size of table is N*logN jumps are made in order of powers of 2 ->1,2,4...etc trying to divide by 2 let mid=par[i][k-1] (2^(k-1)th parent if exists) par[i][k] is par[mid][k-1] Its basically dividing a big jump into 2. First make 2 nodes that we are going to find LCA to same depth using Walk function if current jump results -1 then we have jumped of the table.

Math facts

Segmented Sieve Use When we have to generate large number of prime Numbers Click Here BitHacks Number of bits required to represent a number: For More Bit Tricks:Click Here Useful nCr Technique Divide by their GCD’s to prevent overflow For fast Calculation: ll NcR(ll n, ll r) { ll p = 1, k = 1; if (n - r < r) r = n - r; if (r !

Patience Sort

It is an online sorting algorithm aimed to create piles of cards in such a way that piles are in increasing order down wards. It can be used to find LIS in O(NlogN) time. Can also be used to find (minimum)number of distinct LIS. VII dp; for(int i=arr.size()-1;i>=0;--i) { int x=arr[i]; auto it=upper_bound(all(dp),x); if(it==dp.end()) dp.pb(x); else *it=x; } cout<<dp.size();

SCC

Kosaraju’s SCC A strongly Connected Component is for a directed graph. For an undirected graph we say it is a connected Component if we can reach a vertex from any vertex of a connected component. In case of SCC its same but called differently. Steps Perform DFS in forward graph and make a note of nodes in decreasing order of outtime. Perform DFS in reverse graph(instead of for loop use the decreasing order u found).

Template Library

Fenwick Tree #include<bits/stdc++.h>using namespace std; template<typename T> class FenwickTree { vector<T> BIT; int n; public: FenwickTree(int n,vector<T>& arr,T def) { BIT.assign(n + 1, def); this->n = n; } void update(int i,T v) { while (i <= n) BIT[i] += v, i += i & -i; } T query(int i,T def) { //get from 0 to i T sum = def; while(i>0) sum += BIT[i], i -= i & -i; return sum; } }; class RangeFenwickTree { int n; vector<int> BIT1; vector<int> BIT2; public: RangeFenwickTree(int n,vector<int>& arr) { this->n = n; BIT1.

Time Complexity Analysis

General TC Harmonic Sum Analysis When a function goes in the form of for(int i=1;i<=n;++i) { for(int j=2*i;j<=n;j+=i) cout<<(i,j); } The Summation part takes O(logN) hence the total time is O(N*logN) Note: Find Why it is logN

Trees

Some Facts about trees Simple path is a path that doesn’t contain any node twice. A tree has n-1 edges! Segment Trees Use segment trees for questions on updating values and querying. Can be used with complex operations like pairs,sets etc. Find very effecient and faster updating (used to insert too), by Finding path to root from one node. void update(int pos,int val){ pos += k; tree[pos] = val; int odd = 1; //this switches between alternate levels of the segment tree goes upwards while(pos>>=1 >0){ /* use this in case for level switching if(odd) tree[pos] = tree[2*pos] | tree[2*pos+1]; else tree[pos] = tree[2*pos] ^ tree[2*pos+1]; odd = 1-odd; */ tree[pos]=tree[2*pos]+tree[2*pos+1]; } } for(int i=0;i<n;i++){ int val; cin>>val; update(i,val); }