segment tree

My Calendar III Problem [Solved with Segment Tree, Sweep Line]

In this article at OpenGenus, we have solved the Calendar 3 problem that is to find number of conflicting meetings in a given range of time. We have solved this using the concept of Sweep Line and Segment tree with Lazy Propagation.

segment tree

Booking Concert Tickets in Groups [using BIT and Segment Tree]

In this article, we have solved the problem of Booking Concert Tickets in Groups. This involve the concept of Binary Indexed Tree and Segment Tree.

Algorithms

Schedule Events in Calendar Problem [Segment Tree]

In this article, we will discuss the My Calendar 1 problem where we need to schedule events in a calendar such that there is no conflict. This will involve the concept of Segment Tree.

Data Structures

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