Yash Aggarwal - OpenGenus IQ

Octree data structure

Octree is a tree data structure where each internal node has 8 children. An octree is generally used to represent relation between objects in a 3-dimensional space. It is used in 3D computer graphics. Octrees are also used for nearest neighbor search which can be done easily in logarithmic time.

data structure

Palindromic Tree (Eertree)

Palindromic tree (Eertree) is a tree based data structure that is specifically used to tackle problems involving palindromes of a string like 'longest palindrome in a string', 'count of plaindromic substrings'. It keeps track of all palindromic substrings of a string in linear time and space

algorithm

Cartesian tree sorting

Cartesian tree sorting, also called Levcopoulos Petersson algorithm is an adaptive sorting algorithm, i.e. it performs much better on a partially sorted data. It needs two data structures a Cartesian tree and a priority queue. The algorithm here uses min-heap Cartesian tree to give a sorted sequence

data structure

Fusion Tree

Fusion tree is a tree data structure that implements associative array in a known universe size. Fusion trees are used to solve predecessor and successor problem. We have covered sketch, parallel comparison, predecessor and successor and insert operations in O(log N) time and O(N) space complexity

data structure

Quadtree

Quadtree is a tree data structure which is used to represent 2-dimensional space. It finds major applications in computer graphics where it is used to represent relations between objects in a 2D space and for image compression. We discussed point region (PR) quadtree which store points in a 2D space

data structure

Van Emde Boas tree

Van Emde Boas tree is a tree data structure which implements an associative array with m-bit integer keys. It performs all operations (insert, delete, lookup, maximum, minimum, successor and predecessor) in O(log log M) time, where M is the maximum number of elements that can be stored in the tree.

data structure

Y fast trie

Y-fast trie is a data structure used to store integers from a bounded domain. It has two data structures X fast trie and balanced binary search tree with the change being we operate on representative values r in X-fast tries, and the leaf nodes point to balanced binary search trees instead of values

data structure

X-fast trie

X-fast trie is a data structure used to store integers from a bounded domain. It is a bitwise trie, i.e. a binary tree where each subtree stores values having binary representations with common prefix. It is a trie of hash tables and supports successor and predecessor operations in log log U time

data structure

Treap / Randomized cartesian tree

A treap is a height balanced binary tree with heap properties. It is used to store a sequence in a tree, which allows for various applications like searching. It takes O(log N) time complexity for search, insert and delete operations and takes O(N) space complexity

data structure

Cartesian Tree

A Cartesian tree is a binary rooted tree data structure that can answer range queries can be answered by finding least common ancestors in the tree. An inorder traversal of the tree would give the original sequence used to form the tree. It is used as binary search tree for an ordered sequence

data structure

Prefix sum array

Prefix Sum array is a data structure design which helps us to answer several queries such as sum in a given range in constant time which would otherwise take linear time. It requires a linear time preprocessing and is widely used due to its simplicity and effectiveness.

data structure

2D Fenwick Tree / 2D Binary Indexed Tree

Fenwick Tree is used to answer range or interval queries in an array in logarithmic time. Fenwick tree can be generalized to multiple dimensions. 2D Fenwick tree is one such implementation used to answer sub-matrix queries, i.e. queries in 2 dimensions. It requires the operation to be invertible.

data structure

2D Segment Tree

Segment Tree is used to answer range queries in an array. The data structure can be extended to 2 dimensions to answer sub-matrix queries in logarithmic time. Some examples of these queries are Maximum element in sub-matrix It can be seen as a segment tree of segment trees. We give an example for it

data structure

Fenwick Tree (Binary Indexed Tree)

Fenwick Tree / Binary indexed tree (BIT) is a data structure used to process interval/range based queries. Compared to segment tree data structure, Fenwick tree uses less space and is simpler to implement. One disadvantage is that it can be only used with an operation that is invertible.

data structure

Segment Tree

A segment tree is a divide and conquer based data structure used to store information about intervals of some linear data structure. It is a height-balanced binary tree where every node corresponds to an interval of the array. It allows processing interval or range queries in logarithmic time