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.

Segment Tree

What is Segment Tree?

Segment Tree is a data structure that stores data about range of elements in nodes as a tree. It is mostly used to handle range queries with updates in an efficient manner. For example, we can perform a range summation of an array between the range L to R while also modifying the array from range L to R all in log(N) time complexity.

Types of Operations:

The operations that the segment tree can perform must be binary and associative. Some of the examples of operations are:

• Finding Range Sum Queries
• Searching index with given prefix sum
• Finding Range Maximum/Minimum
• Counting frequency of Range Maximum/Minimum
• Finding Range GCD/LCM
• Finding Range AND/OR/XOR
• Finding number of zeros in the given range or finding index of Kth zero

Applications of Segment Tree:

• Interval scheduling: Segment trees can be used to efficiently schedule non-overlapping intervals, such as scheduling appointments or allocating resources.
• Range-based statistics: Segment trees can be used to compute range-based statistics such as variance, standard deviation, and percentiles.
• Image processing: Segment trees are used in image processing algorithms to divide an image into segments based on color, texture, or other attributes.

Basics of Segment Tree:

• Segment Tree meaning in DSA
• Introduction to Segment Trees – Data Structure and Algorithm Tutorials
• Persistent Segment Tree
• Segment tree | Efficient implementation
• Iterative Segment Tree
• Range Sum and Update in Array : Segment Tree using Stack
• Dynamic Segment Trees
• Applications, Advantages and Disadvantages of Segment Tree

Lazy Propagation:

• Lazy Propagation in Segment Tree
• Lazy Propagation in Segment Tree | Set 2
• Flipping Sign Problem

Range Queries:

• Queries to check if any non-repeating element exists within range [L, R] of an Array
• Range Minimum Query
• Querying maximum number of divisors that a number in a given range has
• Min-Max Range Queries in Array
• Range LCM Queries
• Number of primes in a subarray (with updates)
• Range query for Largest Sum Contiguous Subarray
• Range Queries for Longest Correct Bracket Subsequence
• Maximum Occurrence in a Given Range
• Queries to find maximum product pair in range with updates
• Range and Update Query for Chessboard Pieces
• String Range Queries to find the number of subsets equal to a given String
• Binary Array Range Queries to find the minimum distance between two Zeros
• Queries to evaluate the given equation in a range [L, R]
• Find element with maximum weight in given price range for Q queries

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