Segment Tree
The time complexity of range queries over an array, such as sum query over an interval or max number in an interval, is O(n). A segment tree is a data structure that allows answering range queries over an array with a time complexity of O(logn). Between answering such queries the Segment Tree allows modifying the array by replacing one element or even changing the elements of a whole subsegment to a value. Segment Tree can be used to solve a lot of problems involving range queries with efficient time complexity constraints.
Introduction to Segment Trees
By Anant Dhakad
● Published At Jan 2022
In this article, we will see an introduction to segment trees. A segment tree is an advanced data structure used to solve range-based queries.... Keep reading ..
Segment Tree
By Yukti Kumari
● Published At Oct 2021
This article introduces segment trees and explains their implementation to answer range sum queries. ... Keep reading ..
Merge Sort Tree For Range Order Statistics
By Ayush Prakash
● Published At Feb 2022
This blog will discuss an exciting problem: Merge Sort tree for range order statistics. It is based on an advanced data structure called merge sort trees(segment tree). We will discuss the space and time complexity of the approach discussed.... Keep reading ..
Length of Longest Increasing Subsequences (LIS) using Segment Tree
By Anant Dhakad
● Published At Jan 2022
In this article, we will take a coding problem based on the concept of the Longest Increasing Subsequence. We will solve this problem using a segment tree. ... Keep reading ..
Count of Xs in the Array for a given range of indices after array updates for Q queries
By Apoorv
● Published At Feb 2022
This article will discuss the solution for the problem statement ‘Count of Xs in the Array for a given range of indices after array updates for Q queries’.The article will discuss both naive and optimized approaches along with the time and space comp... Keep reading ..
Longest Subarray with GCD Greater than 1
By Ujjawal Gupta
● Published At Jan 2022
In this blog, we will learn to solve a problem based on longest subarray with GCD greater than 1.... Keep reading ..
Count Substrings having Frequency of a Character Exceeding that of Another Character in a String
By Aman kumar Chourasiya
● Published At Jan 2022
In this blog, we will discuss a problem based on segment trees. Segment trees are well known for implementing update and range queries in O(log N) time.... Keep reading ..
Queries to Calculate the Sum of the Array Elements Consisting of an Odd Number of Divisors
By GAZAL ARORA
● Published At Mar 2022
In this article, we will design an algorithm to solve all of the queries about calculating the sum of the elements of an array in a given range with an odd number of divisors.... Keep reading ..
Queries to Calculate Sum of Squares of ASCII Values of Characters of a Substring with updates
By Abhishek Ranjan
● Published At Jan 2022
In this article, we will solve a problem using the segment tree data structure.... Keep reading ..
Queries to calculate sum of squares of array elements over range of indices [L, R] with updates
By Abhishek Ranjan
● Published At Mar 2022
In this article, we will solve an online range query problem using the segment tree data structure with lazy propagation.... Keep reading ..
Range Update in a Segment Tree without using Lazy Propagation and Point Query
By Apoorv
● Published At Feb 2022
This article will discuss the solution to do Range Update in a Segment Tree without using Lazy Propagation and Point Query along with the solution, the article focuses on the time and space complexity of the solution.... Keep reading ..
Queries to Count Array Elements from a Given Range having a Single Set Bit
By Malay Gain
● Published At Jan 2022
In this article, we will learn how to count array elements from a given range having a single set bit. ... Keep reading ..
Queries to Find The First Array Element Exceeding K with Updates
By Malay Gain
● Published At Jan 2022
In this article, we will learn how to to find the first array element exceeding K with updates.... Keep reading ..
Maximize value of a pair from two given arrays based on given conditions
By HET FADIA
● Published At Feb 2022
The blog aims to introduce you to solve a problem having two arrays and some given conditions.... Keep reading ..
Range minimum query
By Malay Gain
● Published At Nov 2021
In this article, we will see how to solve the problem, Range minimum query. ... Keep reading ..
Queries to find the min index in a range [L, R] having at least value ele with updates
By Apoorv
● Published At Feb 2022
This article will discuss the solution of the problem statement “Queries to find the min index in a range [L, R] having at least value ele with updates” along with the solution, the article focuses on the time and space complexity of the solution.... Keep reading ..
Queries to calculate sum with alternating signs of array elements in a given range
By Riya
● Published At Feb 2022
This article will discuss the problem "Queries to calculate sum with alternating signs of array elements in a given range," the solution approach to this problem, its C++ implementation, and its time and space complexity. ... Keep reading ..
Query to find the length of the longest subarray consisting of only 1s
By Ayush Prakash
● Published At Feb 2022
In this blog, we are going to discuss a really interesting problem: Query to find the length of the longest subarray consisting of only 1s. We are going to discuss two approaches, first the naive one and then the efficient solution. We will analyze t... Keep reading ..
Maximize the length of longest subarray consisting of same elements by at most X decrements
By Apoorv
● Published At Feb 2022
This article will discuss the solution of the problem statement "Maximize the length of longest subarray consisting of same elements by at most X decrements" along with the solution. The article focuses on the time and space complexity of the solutio... Keep reading ..
Maximum length of same indexed subarrays from two given arrays satisfying the given condition
By Anant Dhakad
● Published At Jan 2022
This article will take a coding problem based on Binary Search and Segment Tree. A segment tree is an advanced data structure used to solve range-based queries.... Keep reading ..
Queries to Count Array Elements Greater Than or Equal to a given Number with Updates
By Anant Dhakad
● Published At Jan 2022
This article will take a coding problem based on Arrays. Array-based questions are very prevalent in interviews/coding rounds.... Keep reading ..
Maximize sum of array by reducing array elements to contain no triplets (i, j, k) where a[i] < a[j] and a[i] < a[k] and j <i < k
By Jaglike Makkar
● Published At Feb 2022
In this article we will discuss the approach to maximize the sum of array by reducing its elements by 1 such that it contains no triplets (i,j,k) where a[i] < a[j] and a[i] < a[k] and j < i < k along with it’s space and time complexities.... Keep reading ..
Queries to Evaluate the given Expression in a range [L, R]
By Riya
● Published At Feb 2022
This article will discuss the problem "Queries to evaluate the given equation in a range [L, R]," the solution approach to this problem, its C++ implementation, and its time and space complexity.... Keep reading ..
puzzle icon

Top Problems related to Segment Tree