segment tree

Li Chao Segment Tree

In this article, we discuss the Li Chao tree, a segment tree which can be persistent and is faster in practice compared to the convex hull trick.

Data Structures

Persistent Segment Tree

Our aim is to introduce persistency in segment trees but also ensure that the space and time complexity is not affected.

Data Structures

Optimizing a Segment Tree with Lazy Propagation

Lazy propagation is an optimization technique for segment tree to delay some of the update queries so that a set of update queries can be performed more efficiently together and thus, reducing the number of operations performed. The time complexity remain the same.

Data Structures

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 Structures

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