×
Home Discussions Write at Opengenus IQ
×
  • Track your progress
  • Deep Learning Projects
  • Python Projects
  • Join our Internship 🎓
  • RANDOM
  • 100+ Graph Algorithms
  • 100+ DP Problems
  • 50+ Linked List Problems
  • 50+ Array Problems
  • One Liner
  • 50+ Binary Tree problems
  • Home
  • Rust Projects

segment tree

A collection of 5 posts

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.

Erick Lumunge
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.

Siddharth Agarwal Siddharth Agarwal
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.

Siddharth Agarwal Siddharth Agarwal
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

Yash Aggarwal Yash Aggarwal
Data Structures

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

Yash Aggarwal Yash Aggarwal
OpenGenus IQ © 2023 All rights reserved â„¢ [email: team@opengenus.org]
Top Posts LinkedIn Twitter