Range Query

In Range Query problems, we commonly are given an array of N integers and Q queries of one or more types. The range [L, R] of the query will also be given, and based on it, we will have to perform some function on the given array.
Prefix Arrays, Segment Trees, Fenwick Trees, Mo's Algorithm are the various efficient methods to solve Range Query problems.

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

Fenwick Tree

Fenwick Tree, also known as Binary Indexed Tree (BIT), provides an efficient way to compute prefix sum on an array allowing array modification. Consider an array A of size N. We need to perform two kinds of operations on this array:
1. Modify array element at index i
2. Compute prefix sum up to index i One efficient solution is to use segment tree that can perform both operations in O(logn) time. But then why learn Fenwick Tree data structure when we already have a solution. It is because Binary Indexed Trees require less space and are very easy to implement.

Find Value After N Operations to Remove N Characters of String S with Given Constraints

By Malay Gain

● Published At Jan 2022

In this article, we will learn how to find value after N operations to remove N characters of string S with given constraints.... Keep reading ..

Sum of previous numbers that are greater than current number for given array

By Anant Dhakad

● Published At Jan 2022

In this article, we will take a coding problem based on the application of the Fenwick Tree, also known as the Binary Indexed Tree. Fenwick trees are used to calculate prefix sum efficiently and handle updates efficiently.... Keep reading ..

Finding XOR of the Array Elements in a Given Range with Updates using Fenwick Tree

By GAZAL ARORA

● Published At Mar 2022

In this article, we will design an algorithm to solve the queries of finding the XOR of array elements in a given range with updates of array values using the Fenwick Tree.
... Keep reading ..

Queries for the Number of Nodes having Values Less than V in the Subtree of a Node

By Anant Dhakad

● Published At Jan 2022

In this article, we will take a coding problem based on the application of the Fenwick Tree, also known as the Binary Indexed Tree. Fenwick trees are used to calculate prefix sum efficiently and handle updates efficiently. ... Keep reading ..

Count smaller elements on right side and greater elements on left side using Binary Index Tree

By Anant Dhakad

● Published At Jan 2022

In this article, we will take a coding problem based on the application of the Fenwick Tree, also known as the Binary Indexed Tree. Fenwick trees are used to calculate prefix sum efficiently and handle updates efficiently. ... Keep reading ..

Find the Number of Pair of Ideal Nodes in a Given Tree

By Riya

● Published At Feb 2022

This article will discuss the problem "Find the number of pair of ideal nodes in a given tree", an approach to solve this problem, its C++ implementation, and time and space complexity.... Keep reading ..

Range Sum Queries and Update with Square Root

By Soumya Agrawal

● Published At Mar 2022

This article will cover the approach and implementation of the problem- Range Sum Queries and Update with Square Root.... Keep reading ..

Number of elements greater than K in the range L to R using Fenwick Tree (Offline queries)

By Jaglike Makkar

● Published At Feb 2022

This article will discuss finding the number of elements greater than K from index L to R for offline queries using the Fenwick Tree. We will also focus on the complexity of our solution.... Keep reading ..

Count of Inversion of size K in a given array

By Riya

● Published At Feb 2022

This article will discuss the problem "Count of Inversions of size K in a given array," an approach to solve this problem, its C++ implementation, and time and space complexity.... Keep reading ..

XOR of Numbers that Appeared Even Number of Times in Given Range

By Anant Dhakad

● Published At Jan 2022

In this article, we will take a coding problem based on the application of the Fenwick Tree, also known as the Binary Indexed Tree. Fenwick trees are used to calculate prefix sum efficiently and handle updates efficiently. ... Keep reading ..

Sum of Interval and Update with Number of Divisors

By Jaglike Makkar

● Published At Feb 2022

In this article, we will discuss the approach to find the sum of a segment of an array and update a segment by replacing every number with its number of divisors for multiple queries. We will also focus on the complexity of our approach.... Keep reading ..

Maximum Sum of Increasing Subsequence using Fenwick Tree

By Apoorv

● Published At Feb 2022

This article will discuss the solution for finding the Maximum Sum of Increasing Subsequence using Fenwick Tree along with the solution; the article focuses on the time and space complexity of the solution.... Keep reading ..

Queries for Number of Distinct Elements in the Subarray

By Jaglike Makkar

● Published At Feb 2022

In this article, we will discuss the approach to finding the number of distinct elements in the subarray for multiple queries. We will also focus on the complexity of our approach.... Keep reading ..

Number of Elements less than or equal to a given number in a given subarray

By Riya

● Published At Feb 2022

This article will discuss the problem "Find the number of elements less than or equal to a given number in a given subarray, its C++ implementation, and time and space complexity.... Keep reading ..

Count Inversions using Fenwick Tree

By SHIKHAR SONI

● Published At Jan 2022

The article covers the use of the Fenwick tree to determine the inversion count in an array... Keep reading ..

Two Dimensional Fenwick Tree

By Apoorv

● Published At Feb 2022

This article will discuss the Two Dimensional Fenwick Tree concept and its application and its space and time complexity.... Keep reading ..

Binary Indexed Tree or Fenwick Tree

By Malay Gain

● Published At Nov 2021

In this article, we will learn Binary Indexed Tree or Fenwick Tree.
... Keep reading ..

Binary Indexed Tree or Fenwick Tree

By Abhishek Ranjan

● Published At Jan 2022

In this article, we will discuss Binary Index Tree/Fenwick Tree and see its implementation in c++.... Keep reading ..

Range Update and Range Queries in Binary Indexed Tree

By Riya

● Published At Mar 2022

This article will discuss "Range update and Range Queries in Binary Indexed Tree," its C++ implementation, and time and space complexity.... Keep reading ..

Binary Indexed Tree: Range Update and Range Queries

By Shreya Deep

● Published At Jan 2022

This article describes the methods to do range update and range queries on a binary indexed tree... Keep reading ..

Querying the Number of Distinct Colors in a Subtree of a Colored Tree using BIT

By Abhishek Ranjan

● Published At Jan 2022

This article will solve a problem on trees using the binary index tree/Fenwick tree. Through this article, we will learn an algorithm to flatten the given tree and see an application of the binary index tree.... Keep reading ..

Minimum Possible Integer After at Most K Adjacent Swaps On Digits

By Ujjawal Gupta

● Published At Mar 2022

In this blog, we will discuss an interesting interview problem, namely the minimum possible integer after at most K adjacent swaps on digits. It is a Leetcode Hard problem.... Keep reading ..

The Skyline Problem

By Rhythm Jain

● Published At Nov 2021

This article discusses The Skyline Problem, which is one of the most challenging questions asked in interviews of tech giants. ... Keep reading ..

Sparse Table

SEAD Problem (Codechef)

By SHIKHAR SONI

● Published At Mar 2022

This article discusses the ‘SEAD’ problem on CodeChef and its approach.... Keep reading ..

Matchstick Problem

By GAZAL ARORA

● Published At Mar 2022

In this article, we will design an algorithm to solve the queries about the time taken in burning all the matchsticks.
... Keep reading ..

Monster Kill

By Sujal Modanwal

● Published At Mar 2022

The task is to find out the longest consecutive subsegment satisfying the mentioned conditions.... Keep reading ..

Find the S-value of the Given Subarrays Using Mo’s Algorithm

By Abhishek Ranjan

● Published At Mar 2022

This article will solve a range query problem using square root decomposition/Mo's algorithm.... Keep reading ..

SQRT Decomposition

Tree and Queries

By Ujjawal Gupta

● Published At May 2022

In this blog, we will learn to solve a problem based on queries on the tree.... Keep reading ..

Mex Puzzle

By Saksham Gupta

● Published At Mar 2022

This blog will discuss how we can solve a problem - Mex Puzzle.
... Keep reading ..

XOR and Lucky Number

By Saksham Gupta

● Published At Mar 2022

This blog will discuss how we can solve a problem - XOR and Lucky Number.
... Keep reading ..

Ninja’s Messenger

By Riya

● Published At Mar 2022

This article will discuss the problem “Ninja’s Messenger,” solution approach to the problem, its C++ implementation, and its time and space complexities.... Keep reading ..

Frequency Range Count

By Ujjawal Gupta

● Published At Mar 2022

In this blog, we will learn to solve a problem based on the Range theory.... Keep reading ..

Coprime Queries on Trees

By Sujal Modanwal

● Published At Mar 2022

For a given tree with N nodes, the task is to solve the given queries.... Keep reading ..

Count on a Tree - 2

By Sujal Modanwal

● Published At Mar 2022

In this article, we will learn the way to find the number of distinct node values in a path between two nodes.... Keep reading ..

Sqrt (Square Root) Decomposition

By Riya

● Published At Mar 2022

This article will discuss the concept of “sqrt decomposition” and the solution of an example problem using “sqrt decomposition”, its C++ code, and its time and space complexity.... Keep reading ..

Sum of All Elements With Odd Frequency in the Given Subarray

By Ujjawal Gupta

● Published At Jan 2022

In this blog, we will learn to solve a problem based on a range query, the sum of all elements with odd frequency in the given subarray.... Keep reading ..

Mo's Algorithm

By Saksham Gupta

● Published At Mar 2022

This blog will discuss a famous competitive programming algorithm - Mo’s Algorithm.
... Keep reading ..

Mo's Algorithm With Updates (SUM query)

By Saksham Gupta

● Published At Mar 2022

This blog will discuss a variation famous competitive programming algorithm - Mo’s Algorithm with Updates.
... Keep reading ..

DQUERY - SPOJ

By Sujal Modanwal

● Published At Mar 2022

The article describes how to find the number of distinct elements in the given range.... Keep reading ..

Mo’s On Trees and SQRT Decomposition

By Sujal Modanwal

● Published At Mar 2022

In this article, you will learn about Mo’s algorithm and SQRT Decomposition for trees... Keep reading ..

## Top Problems related to Range Query

Arithmetic Progression Queries

Reverse Pairs

Order of People Heights

Selecting Three People

Boxes and chocolates

Ninja and Meteorites

Count of Smaller Elements

Create Sorted Array through Instructions

Online Majority Element In Subarray

Range Sum Query - Mutable

Smallest Integer After K Adjacent Swaps

Fastest Horse

Maximum Subarray Sum Queries - ll

Maximum Subarray Sum Queries

Binary Flip

Squares Sum

Count Even Or Odd

Ninja and Time

Ninja Land

Range Minimum Query