Graph Theory

Number Theory

String

Backtracking

Search Technique

• Disjoint Set

• Binary Indexed Tree / Fenwick Tree

  • 1D BIT
    • Point Update , Range Query , lower_bound , upper_bound
      update , query : O(logN)
      lower_bound , upper_bound : binary search - O( (logN)^2 ) , binary lifting - O(logN)
    • Range Update , Point Query
      update , query : O(logN)
  • 2D BIT
    • Point Update , Range Query

• Recursive Segment Tree

  • Non Lazy (Point Update , Range Query)

    build : O(N) update , query : O(logN) 

    • Range Sum ( Possible Variations : Range [ Multiplication , Min , Max , GCD , LCM , and , or , xor ] )
    • Maximum Prefix Sum & Maximum Suffix Sum & Maximum Contiguous SubArray Sum
  • Lazy (Range Update , Range Query)

    build : O(N) update , query : O(logN) 

    • Range Assignment Update , Range Sum Query
    • Range Increment Update , Range Sum Query
    • Range Increment Update , RMQ
    • Range Flip Update , Range Sum Query
  • Merge Sort Tree
    • Range Query

      build : O( NlogN ) query : O( (logN)^2 ) memory : O( NlogN ) 

    • Point Update , Range Query

      build : O( N (logN)^2 ) update , query : O( (logN)^2 ) memory : O( NlogN ) 

• Iterative Segment Tree

  • Non Lazy

    build : O(N) update , query : O(logN) 

    • Point Update , Range Query ( Possible Variations : Range [ Multiplication , Min , Max , GCD , LCM , and , or , xor ] )
    • Range Update , Point Query

• Sweep Line Algorithm

• Mo's Algorithm (Square Root Decomposition)

  • Range Sum Query
  • Range Mode (Highest Frequency) Query

• Suffix Array

  • O( N^2 logN )
  • O( N (logN)^2 )
  • O( NlogN )
  • O( NlogN ) optimized

• Priority Queue

• STL

  • Set
  • Map

• Policy Based Data Structure

  • Set
  • Multiset
    • Implementation 1 (erase doesn't work)
    • Implementation 2

• LCS Variant
  • Longest Common Subsequence
  • Longest Palindromic Subsequence
  • Longest Repeated Subsequence
  • Levenshtein / Edit Distance
  • Shortest Common Supersequence
• LIS Variant
  • Longest Increasing Subsequence
  • Longest Bitonic Subsequence
  • Increasing Subsequence with Maximum Sum
  • Longest Increasing Index-Dividing Subsequence
• Coin Change
  • Coin Change (Minimum number of coins to make a sum)
  • Coin Change (Number of ways to make a sum)
  • LightOj 1079 (Just Another Robbery)
• Matrix Variant
  • Largest Square Matrix with all 1's
  • Minimum Cost Matrix Path (Top Left cell to Bottom Right cell)
  • Number of paths in a matrix with certain cost (Top Left cell to Bottom Right cell)
  • Longest Sequence formed by adjacent numbers in a matrix
  • 2 Way Prefix Sum (LightOj)
• Knapsack Variant
  • 0-1 Knapsack
  • Partition Problem
  • Minimum Sum Partition Problem
• Digit DP Variant
  • Number of zeros (LightOj)
  • Odd Sum Even Sum (SPOJ)
  • Digit Min Max Scores (HackerRank)
  • Adjacent 1 Scores in binary (LightOj)
  • Divisibility check by Digit Sum (LightOj)
  • Digit Sum (SPOJ)
  • Encoding (CodeChef)
• Bitmask DP
  • Bitmask DP 1 [ LightOj 1011 (Marriage Ceremonies) ]
  • Bitmask DP 2 [ LightOj 1018 (Brush IV) ]
  • Bitmask DP 3 [ LightOj 1037 (Agent 47) ]
  • Bitmask DP 4 [ LightOj 1057 (Collecting Gold) ]
• Miscellaneous
  • N-digit binary strings without any consecutive 1’s

• Operator Overloading for sorting / STL Data Structure

  • Using Comparator
  • Overloading < operator
  • Overloading > operator

• Geometry Template

  • Point & Line
  • Rectangle

Computer Science & Engineering Department , BUET