Sahil Dua

A segment tree is a tree data structure that allows aggregation queries and updates over array intervals in logarithmic time. As I see it, there are three major use cases for segment trees:

1. Static or persistent segment trees: This is probably the most common use case. We preprocess an array of N elements to construct a segment tree in O(N). Now, we can query aggregates over any arbitrary range/segment of the array in O(log N).
2. Segment tree with point updates: This allows us to update array values, one at a time in O(log N), while still maintaining the segment tree structure. Queries over any arbitrary range still occurs in O(log N).
3. Segment tree with range updates: This allows us to update a range of array elements at once in O(N) in the worst case, however problem specific optimizations and lazy propagation typically give huge improvements. Queries over any arbitrary range still occurs in O(log N).

In this post, I’ll…

You may have wondered about the vast and endless nature of topics important(or I should say sufficient) for competitive programming point of view. Well to sum it all I have prepared a list(huge one!!!). It contains all the famous problems,algorithms and data structure…………………………

(a)Number Theory

1. Prime Number Generation  (Sieve, Segmented Sieve)
2. Euler Totient Theorem
3. Fermat’s Theorem
4. HCF & LCM (Euclid)
5. Linear Diophantine Equations (Extended Euclid)
6. Modulus Arithmetic (addition,multiplication,subtraction,modular Inverse)
7. Cycle Finding (Floyd Algo and Brent Algo)
8. Integer Factorization (Trial Division , Pollard Rho method)
9. Lucas Theorem  (Simple & Advance)
10. Chinese Remainder Theorem
11. Wilson Theorem
12. Miller – Rabin Primality Testing
13. Perfect Numbers
14. Goldbach Conjecture

(b)Probability

1. Basic Probability and Conditional Probability
2. Random Variables
3. Probability Generating Functions
4. Expectation
5. Probability Distribution [Binomial, Poisson, Normal,Bernoulli]

(c)Counting

1. Pigeonhole principle
2. Inclusion Exclusion
3. Special Numbers  [Stirling,Fibonacci,Catalan, Eulerian, Harmonic, Bernoulli]
4. Polya Counting
5. Burnside lemma

(d)Permutation Cycles

(e)Linear Algebra

1. Addition And Subtraction Of Matrices
2. Multiplication ( Strassen’s algorithm ), Logarithmic…

Suffix Arrays

It is the data structure to look out for when you are going for string Searching and want to reduce the time complexity greatly.  So, Let us examine and start from basics.

What are Suffix Arrays ?

As simple as it can get , suffix arrays represent the rank of all possible suffixes of a given string .For example ,

String  S = “ABDCASD”

Then the suffixes for the string S (with the numbers in front represent are ,

7 $ *

6 D

5 SD

4 ASD
3 CASD

2 DCASD

1 BDCASD

0 ABDCASD

*$, A null character can be called a suffix of every string as it does no addition to the string itself . We will later on see why we chose to add NULL character to our algorithm . For NULL character that we used, we assume have highest lexicographic priority .

Now,

Hi there fellas. Today i am going to list 20 python libraries which have been a part of my toolbelt and should be a part of yours as well. So here they are