data-structures-and-algorithms-in-c--

this contains different types of data structures and algorithms implemented in c++

Index :

This site was built using GitHub Pages.

number theory :

   1. ncr mod prime 

normal , CP.

   2. sieve of eratosthenes

normal , CP. 3. segment sieve of eratosthenes normal , CP. 4. order statistics -> 'kth smallest in array' in linear time

Graph theory :

  1.Disjoint set union -> implementation of DS and cycle detection and no of connected components
  2.undirected graph cycle detection  
  3.find undirected graph cycle (print cycle)
  4.find directed graph cycle (print cycle)
  5.multiple query lca using euler tour and range min query

advanced data structures : with easy modification and implemented in OOP style

1. segment trees ( range (min , max , sum ) ) - multiple range queries and point updates - O(nlogn + Qlogn) 
2. Binary indexed trees - (range ( sum ) ) - range query and point updates O(n + Qlogn)
3. sparse table (range (min , max)) - range query in O(1) - no updates - O(nlogn + Q*1) 
4. suffix array class - suffix_array and lcp array construction in O(nlogn)