Skip to content

Latest commit

 

History

History
67 lines (32 loc) · 1.61 KB

README.md

File metadata and controls

67 lines (32 loc) · 1.61 KB
Raw

Advanced-Intrusive

This library contains code related some of the advanced data structures useful to the modern world.

This Project adds 4 advanced data structures into the collection:-

  1. Segment tree

  2. Fenwick tree

  3. Suffix tree

  4. Suffix automata

As a part of project 2 more algorithms are also implemented.

  • Heavy light decomposition

  • Centroid decomposition

Segment tree

Segment tree implemented here is basic version which supports all the basic methods.The methods are:-

-Build() -Update() -Query()

This also supports iterator.

Fenwick tree

Fenwick tree implemented here is basic version which supports all the basic methods.The methods are:-

-Build() -Update() -Query()

This also supports iterator.This data structure can be extended by adding advanced methods.

Suffix tree

Suffix tree is used in lot of string applications.It can solve many string based problems.The method supported by suffix tree implemented here are:-

-Build()

Suffix automata

Suffix automata is used in lot of string applications.It can solve many string based problems.The method supported by suffix automata implemented here are:-

-Build()

Heavy light decomposition

This is a popular type of decomposition where every node selects a heavy child thus forming chains.The important advantage is we can travel between any 2 nodes in just O(log(N)) chains.This can be used in many tree based problems.

Centroid decomposition

This is also popular decomposition where in we recursively select centroid and remove it forming forest and then selecting centroid among those trees.This gives a tree of height O(log(N)).