Запросы элементов, имеющих значения в диапазоне от A до B в заданном диапазоне индексов, с использованием дерева сегментов

Опубликовано: 1 Декабря, 2021

Для массива arr [] из N элементов и двух целых чисел от A до B задача состоит в том, чтобы ответить на Q запросов, каждый из которых содержит два целых числа L и R. Для каждого запроса задача состоит в том, чтобы найти количество элементов в подмассиве arr [L… R], который находится в диапазоне от A до B (оба включены).
Примеры:

Input: arr[] = {7, 3, 9, 13, 5, 4}, A=4, B=7 
query = { 1, 5 } 
Output: 2 
Explanation : 
Only 5 and 4 lies within 4 to 7 
in the subarray {3, 9, 13, 5, 4}.

Input: arr[] = {0, 1, 2, 3, 4, 5, 6, 7}, A=1, B=5 
query = { 3, 5 } 
Output: 3 
Explanation : 
All the elements 3, 4 and 5 lies within 1 to 5 
in the subarray {3, 4, 5}.

Предпосылка: дерево сегментов
Наивный подход: найдите ответ на каждый запрос, просто пройдя массив от индекса L до R и продолжая добавлять 1 к счетчику, когда элемент массива находится в диапазоне от A до B. Время Сложность этого подхода будет O (n * q) .

Эффективный подход:
Постройте дерево сегментов.
Представление сегментных деревьев
1. Узлы-листы - это элементы входного массива.
2. Каждый внутренний узел содержит количество листьев, которое находится в диапазоне от A до B всех листьев под ним.

Построение дерева сегментов из заданного массива
Начнем с отрезка arr [0. . . п-1]. и каждый раз, когда мы делим текущий сегмент на две половины (если он еще не стал сегментом длины 1), а затем вызываем одну и ту же процедуру на обеих половинах, и для каждого такого сегмента мы сохраняем количество элементов, которые находятся внутри диапазон от A до B всех узлов под ним.
Временная сложность этого подхода будет O (q * log (n))

Ниже представлена реализация описанного выше подхода:

C ++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Procedure to build the segment tree
void buildTree(vector< int >& tree, int * arr,
int index, int s, int e, int A, int B)
{
// Reached the leaf node
// of the segment tree
if (s == e) {
if (arr[s] >= A && arr[s] <= B)
tree[index] = 1;
else
tree[index] = 0;
return ;
}
// Recursively call the buildTree
// on both the nodes of the tree
int mid = (s + e) / 2;
buildTree(tree, arr, 2 * index, s, mid, A, B);
buildTree(tree, arr, 2 * index + 1, mid + 1, e, A, B);
tree[index] = tree[2 * index] + tree[2 * index + 1];
}
// Query procedure to get the answer
// for each query l and r are query range
int query(vector< int > tree, int index, int s,
int e, int l, int r)
{
// out of bound or no overlap
if (r < s || l > e)
return 0;
// Complete overlap
// Query range completely lies in
// the segment tree node range
if (s >= l && e <= r) {
return tree[index];
}
// Partially overlap
// Query range partially lies in
// the segment tree node range
int mid = (s + e) / 2;
return (query(tree, 2 * index, s, mid, l, r)
+ query(tree, 2 * index + 1, mid + 1, e, l, r));
}
// Driver code
int main()
{
int arr[] = { 7, 3, 9, 13, 5, 4 };
int n = sizeof (arr) / sizeof (arr[0]);
vector< int > tree(4 * n + 1);
int L = 1, R = 5, A = 4, B = 7;
buildTree(tree, arr, 1, 0, n - 1, A, B);
cout << query(tree, 1, 0, n - 1, L, R)
<< endl;
return 0;
}

Ява

// Java implementation of the approach
class GFG{
// Procedure to build the segment tree
static void buildTree( int tree[] , int arr[] ,
int index, int s, int e,
int A, int B)
{
// Reached the leaf node
// of the segment tree
if (s == e)
{
if (arr[s] >= A && arr[s] <= B)
tree[index] = 1 ;
else
tree[index] = 0 ;
return ;
}
// Recursively call the buildTree
// on both the nodes of the tree
int mid = (s + e) / 2 ;
buildTree(tree, arr, 2 * index,
s, mid, A, B);
buildTree(tree, arr, 2 * index + 1 ,
mid + 1 , e, A, B);
tree[index] = tree[ 2 * index] +
tree[ 2 * index + 1 ];
}
// Query procedure to get the answer
// for each query l and r are query range
static query( int int tree[], int index, int s,
int e, int l, int r)
{
// Out of bound or no overlap
if (r < s || l > e)
return 0 ;
// Complete overlap
// Query range completely lies in
// the segment tree node range
if (s >= l && e <= r)
{
return tree[index];
}
// Partially overlap
// Query range partially lies in
// the segment tree node range
int mid = (s + e) / 2 ;
return (query(tree, 2 * index,
s, mid, l, r) +
query(tree, 2 * index + 1 ,
mid + 1 , e, l, r));
}
// Driver code
public static void main (String []args)
{
int arr[] = { 7 , 3 , 9 , 13 , 5 , 4 };
int n = arr.length;
int tree[] = new int [( 4 * n + 1 )];
int L = 1 , R = 5 , A = 4 , B = 7 ;
buildTree(tree, arr, 1 , 0 , n - 1 , A, B);
System.out.print(query(tree, 1 , 0 , n - 1 , L, R));
}
}
// This code is contributed by chitranayal

Python3

# Python3 implementation of the approach
# Procedure to build the segment tree
def buildTree(tree,arr,index, s, e, A, B):
# Reached the leaf node
# of the segment tree
if (s = = e):
if (arr[s] > = A and arr[s] < = B):
tree[index] = 1
else :
tree[index] = 0
return
# Recursively call the buildTree
# on both the nodes of the tree
mid = (s + e) / / 2
buildTree(tree, arr, 2 * index, s, mid, A, B)
buildTree(tree, arr, 2 * index + 1 , mid + 1 , e, A, B)
tree[index] = tree[ 2 * index] + tree[ 2 * index + 1 ]
# Query procedure to get the answer
# for each query l and r are query range
def query(tree, index, s, e, l, r):
# out of bound or no overlap
if (r < s or l > e):
return 0
# Complete overlap
# Query range completely lies in
# the segment tree node range
if (s > = l and e < = r):
return tree[index]
# Partially overlap
# Query range partially lies in
# the segment tree node range
mid = (s + e) / / 2
return (query(tree, 2 * index, s, mid, l, r)
+ query(tree, 2 * index + 1 , mid + 1 , e, l, r))
# Driver code
if __name__ = = '__main__' :
arr = [ 7 , 3 , 9 , 13 , 5 , 4 ]
n = len (arr)
tree = [ 0 ] * ( 4 * n + 1 )
L = 1
R = 5
A = 4
B = 7
buildTree(tree, arr, 1 , 0 , n - 1 , A, B)
print (query(tree, 1 , 0 , n - 1 , L, R))
# This code is contributed by mohit kumar 29

C #

// C# implementation of the approach
using System;
class GFG{
// Procedure to build the segment tree
static void buildTree( int [] tree, int [] arr,
int index, int s, int e,
int A, int B)
{
// Reached the leaf node
// of the segment tree
if (s == e)
{
if (arr[s] >= A && arr[s] <= B)
tree[index] = 1;
else
tree[index] = 0;
return ;
}
// Recursively call the buildTree
// on both the nodes of the tree
int mid = (s + e) / 2;
buildTree(tree, arr, 2 * index,
s, mid, A, B);
buildTree(tree, arr, 2 * index + 1,
mid + 1, e, A, B);
tree[index] = tree[2 * index] +
tree[2 * index + 1];
}
// Query procedure to get the answer
// for each query l and r are query range
static int query( int [] tree, int index, int s,
int e, int l, int r)
{
// Out of bound or no overlap
if (r < s || l > e)
return 0;
// Complete overlap
// Query range completely lies in
// the segment tree node range
if (s >= l && e <= r)
{
return tree[index];
}
// Partially overlap
// Query range partially lies in
// the segment tree node range
int mid = (s + e) / 2;
return (query(tree, 2 * index,
s, mid, l, r) +
query(tree, 2 * index + 1,
mid + 1, e, l, r));
}
// Driver code
public static void Main ()
{
int [] arr = new int [] { 7, 3, 9, 13, 5, 4 };
int n = arr.Length;
int [] tree = new int [(4 * n + 1)];
int L = 1, R = 5, A = 4, B = 7;
buildTree(tree, arr, 1, 0, n - 1, A, B);
Console.Write(query(tree, 1, 0, n - 1, L, R));
}
}
// This code is contributed by sanjoy_62
Выход:
 2

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Technical Scripter C++ Олимпиады по программированию

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Количество чисел между L и R, взаимно простых с P
27 Февраля, 2023
Постройте матрицу, каждая строка и столбец которой содержат N и M единиц соответственно.
27 Февраля, 2023
Максимизируйте сумму трех чисел, выполнив побитовое XOR
27 Февраля, 2023
Проверьте, совпадает ли набор первых элементов X одного массива с набором первых элементов Y другого
27 Февраля, 2023
Подсчитать подстроки нечетной длины с медианой, такой же, как K-й символ строки
27 Февраля, 2023
Найти лексикографически первый идентификатор каждого домена из заданного массива идентификаторов электронной почты
27 Февраля, 2023
Найдите общее количество фигур 'X'
26 Февраля, 2023
Максимальное значение узла, которое может быть достигнуто с использованием данных соединений
26 Февраля, 2023