█▀▀ █▀█ ▄▀█ █▀█ █░█   ▀█▀ █░█ █▀▀ █▀█ █▀█ █▄█
█▄█ █▀▄ █▀█ █▀▀ █▀█   ░█░ █▀█ ██▄ █▄█ █▀▄ ░█░

█▄░█ █░█ █▀▄▀█ █▄▄ █▀▀ █▀█   ▀█▀ █░█ █▀▀ █▀█ █▀█ █▄█
█░▀█ █▄█ █░▀░█ █▄█ ██▄ █▀▄   ░█░ █▀█ ██▄ █▄█ █▀▄ ░█░

█▀ ▀█▀ █▀█ █ █▄░█ █▀▀
▄█ ░█░ █▀▄ █ █░▀█ █▄█

█▀█ █▀▀ █▀▀ █░█ █▀█ █▀ █ █▀█ █▄░█   ▄▀█ █▄░█ █▀▄
█▀▄ ██▄ █▄▄ █▄█ █▀▄ ▄█ █ █▄█ █░▀█   █▀█ █░▀█ █▄▀

█▄▄ ▄▀█ █▀▀ █▄▀ ▀█▀ █▀█ ▄▀█ █▀▀ █▄▀ █ █▄░█ █▀▀
█▄█ █▀█ █▄▄ █░█ ░█░ █▀▄ █▀█ █▄▄ █░█ █ █░▀█ █▄█

█▄▄ █ ▀█▀
█▄█ █ ░█░

█▀ █▀▀ ▄▀█ █▀█ █▀▀ █░█  
▄█ ██▄ █▀█ █▀▄ █▄▄ █▀█  

▀█▀ █▀▀ █▀▀ █░█ █▄░█ █ █▀█ █░█ █▀▀
░█░ ██▄ █▄▄ █▀█ █░▀█ █ ▀▀█ █▄█ ██▄

• Disjoint Set

• Fenwick Tree / Binary Indexed Tree

  • 1D BIT

    point update : O(logN)
    prefix sum array update : O(logN)

    • Point Update , Range Query , lower_bound , upper_bound

      lower_bound , upper_bound
      --------------------------
      binary search  - O( (logN)^2 )
      binary lifting - O(logN)

    • Range Update , Point Query
  • 2D BIT

    point update : O( (logN)^2 )
    2D prefix sum array update : O( (logN)^2 )

    • Point Update , Range Query
    • Range Update , Point 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

• Implicit Segment Tree

• AVL Tree

• Red Black Tree

• Treap

  • Classic Implementation
  • Implicit Treap
    • Range Update , Range Query
    • Cut Array Portions and Swap
    • Range Delete or Insert , Palindrome Check

• Hash Table

  • Separate Chaining
  • Open Addressing (Double Hashing , Custom Probing)

• Sparse Table

  • Range Sum Query : O(logN)
  • RMQ : O(1)

• Sweep Line Algorithm

• Mo's Algorithm (Square Root Decomposition)

  Total Complexity : O ( (N+Q)F * sqrt(N) )
  where O(F) is the complexity of add and remove function

  • Range Sum Query
  • Range Mode (Highest Frequency) Query
  • Range Mode Sum (Sum of all element with highest frequency) Query
  • Range Number of Distinct Elements 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
    • O(N^2)
    • O( NlogN ) Binary Search
    • O( NlogN ) Segment Tree
  • Longest Bitonic Subsequence
  • Increasing Subsequence with Maximum Sum
  • Longest Increasing Index-Dividing Subsequence
  • Longest Common Increasing Subsequence
    • O( N^3 )
    • O( N^2 )
• 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 functions / structure
  • Overloading < operator
  • Overloading > operator

• Coordinate Compression

• BIG Integer Library

• Integer Root

  • Square Root (Binary Search) (Modifiable to nth Root)
  • Fast Square & Cube Root

• Geometry Template

  • Point & Line
  • Rectangle

If you like my work, you can also support me by buying me a cup of coffee!

Computer Science & Engineering Department , BUET