Some interesting problem on Segment Tree
- Length of Longest Increasing Subsequences (LIS) using Segment Tree
- Maximize length of longest subarray consisting of same elements by at most K decrements
- Generate original permutation from given array of inversions
- Maximum of all subarrays of size K using Segment Tree
- Build a segment tree for N-ary rooted tree
- Length of Longest Subarray with same elements in atmost K increments
- Count number of increasing sub-sequences : O(NlogN)
- Calculate the Sum of GCD over all subarrays
- Cartesian tree from inorder traversal
- LIS using Segment Tree
- Reconstructing Segment Tree
Segment Tree
Segment Tree is a versatile data structure used in computer science and data structures that allows efficient querying and updating of intervals or segments of an array. It is particularly useful for problems involving range queries, such as finding the sum, minimum, maximum, or any other operation over a specific range of elements in an array. The tree is built recursively by dividing the array into segments until each segment represents a single element. This structure enables fast query and update operations with a time complexity of O(log n), making it a powerful tool in algorithm design and optimization.
Table of Content
- What is Segment Tree?
- Applications of Segment Tree
- Basics of Segment Tree
- Lazy Propagation
- Range Queries
- Some interesting problem on Segment Tree