#All useful codes
##1d Segment tree with lazy propagation :
my solution above calculates number of elements in a given array which are multiples of 3.
qsn link : lightoj.com/volume_showproblem.php?problem=1135.s
##2d segment tree :
As we know 1d segment tree for array queries such as update,range sums etc..
2d segment tree is used for matrix queries.
Queries are of
1) update an element
2) range query like : sum of elements from a to b row and c to d column
complexity of each query is log n * log m. where n= rows and m = columns.
##Bellman Ford :
this algorithm is used to find the shortest distance from source (similar to
dijikstra) . but the complexity is O(VE) .
Bellman ford algo is mainly used to find negative cycles in the graph. but it
do not find the position of negative cycle.
##Floyd warshall :
shortest distance between every two nodes in the entire
graph.
##Set inclusion and Exclusion :
this solution is useful when we deal with all the subsets present in an array.
there are 2^n subsets.
we can generate subsets only when n is smaller .
range of n : n < 20 .
variations : max flow min cut , ford fulkerson algo
calculates nCr with modulo mod.
nCr = n! / ((r!)*(n-r)!)
ncr % mod = n! * inverse(r!) * inverse((n-r)!) % mod
inverse(a) = a ^ (mod -2) where mod must be prime.
Normal sieve upto 10^5 , and to generate prime numbers bigger than that use sam_sieve which is basically segmented sieve. by this,we can generate prime numbers upto range 10^9.
Complexity : O(N)
This algorithm is used to build minimum spanning tree.I used priority
queue in stl which minimized my work :p.
complexity : O(V + ElogE)
##Sprague - grundy numbers :
category : Number theory.
find grundy number for all the heap sizes.
grundy value of non movable states are 0.
generally, g[0] = 0 .
g[i] = minimum number which is not present in the set of all the
grundy numbers where 'i' can move into.
answer will be g[n1] ^ g[n2] ^ g[n3] ....
##stl-comparator function :
we are sorting array of structures here :
priority : lesser value of gold comes first ,
if 2 groups have same amount of gold, take the one with lesser silver ,
similarly bronze.
but if all the three are equal ,
the string "name" with lexicographically bigger will come first.
##Tarzans algorithm :
this is used to find out all the strongly connected components in a
graph. a scc is a part of a graph in which there exists a path from
every node to every other node.
run a dfs to find discovery time and also low time of all nodes .
scc root is the one which has same discovery time and low time .
pop all the elements when we find out the root and which gives us one scc.
complexity : O(V+E).
##Trie tree :
implemented by using linked lists . pretty simple to understand .
A very good technique for pattern searching.
Z- array contains
z[i] = maximum substring length from ith index which is also equal to
prefix of the array .
if we append the pattern at the starting, answer will be equal to all
indexes whose z[i] is equal to length of the pattern.
complexity is O(N)