Practice Problems on Segment Tree

What is a Segment Tree?

A Segment Tree is a data structure that stores information about a range of elements in its nodes. It also allows users to modify the array and perform range queries in smaller complexity. 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....

Structure of the Segment Tree:

The segment tree works on the principle of divide and conquer....

Construction Of Segment Tree:

There are two common approaches to construct a Segment Tree:...

What is Dynamic Segment Tree?

A dynamic Segment tree is the one where the values of the array is not fixed i.e it has an extra operation where the value of the i’th index of the array can be changed. As per this change the segment tree performs dynamic changes to give the right result after the changes have been made....

Querying On Segment Tree:

The below table lists the query type and its time complexity for a segment tree:...

Applications of Segment Trees in Competitive Programming:

In CP, there are many problems which requires querying range data of an array in fast time i.e. about O(log(n)), this is where segment tree comes handy, let us see the most common applications of segment tree during a CP contest:...

Interval Intersection and Union:

Interval intersection and union operations on a segment tree with updates involve maintaining information about intervals and efficiently performing intersection and union operations on them, while also supporting updates to the intervals. It performs 3 operations:...

Advanced Topics and Variations for Segment Tree:

Persistent Segment Trees Two-Dimensional Segment Tree...

Alternative Data Structures for Segment Tree:

Sparse Table Fenwick Tree...

Practice Problems on Segment Tree:

Problem Link Range Minimum Query Solve GCDs of given index ranges in an Array Solve Sum of Query II Solve Queries for elements greater than K in the given index range Solve Queries for number of distinct elements in a subarray Solve Sum of maximum of all subarrays Solve Count elements which divide all numbers in range L-R Solve Kth smallest element in a subarray Solve Nitika and her queries Solve Element left after performing alternate OR & XOR operation Solve Increasing Decreasing Update Queries Solve...