Рубрики

Запросы для элементов больше K в заданном диапазоне индекса с использованием дерева сегментов

Имеется массив arr [] из N элементов и количество запросов, где каждый запрос будет содержать три целых числа L , R и K. Для каждого запроса задача состоит в том, чтобы найти количество элементов в подмассиве arr [L… R] , превышающее K.

Примеры:

Input: arr[] = {7, 3, 9, 13, 5, 4}, q[] = {{0, 3, 6}, {1, 5, 8}}
Output:
3
2
Query 1: Only 7, 9 and 13 are greater
than 6 in the subarray {7, 3, 9, 13}.
Query 2: Only 9 and 13 are greater
than 8 in the subarray {3, 9, 13, 5, 4}.

Input: arr[] = {0, 1, 2, 3, 4, 5, 6, 7}, q[] = {{0, 7, 3}, {4, 6, 10}}
Output:
4
0

Условие: Сегментное дерево

Наивный подход: найдите ответ для каждого запроса, просто пройдя массив от индекса l до r и продолжая добавлять 1 к счетчику всякий раз, когда элемент массива больше k . Сложность времени такого подхода будет O (n * q) .

Эффективный подход: построить дерево сегментов с вектором на каждом узле, содержащим все элементы поддиапазона в отсортированном порядке. Ответьте на каждый запрос, используя дерево сегментов, где можно использовать двоичный поиск , чтобы вычислить, сколько чисел присутствует в каждом узле, поддиапазон которого находится в пределах диапазона запроса, который больше K. Временная сложность этого подхода будет O (q * log (n) * log (n))

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

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Процедура слияния для объединения двух
// векторы в один вектор

vector<int> merge(vector<int>& v1, vector<int>& v2)

{

    int i = 0, j = 0;

  

    // Конечный вектор для возврата

    // после слияния

    vector<int> v;

  

    // Цикл продолжается, пока не достигнет

    // конец одного из векторов

    while (i < v1.size() && j < v2.size()) {

        if (v1[i] <= v2[j]) {

            v.push_back(v1[i]);

            i++;

        }

        else {

            v.push_back(v2[j]);

            j++;

        }

    }

  

    // Здесь просто добавляем оставшиеся

    // элементы вектора v

    for (int k = i; k < v1.size(); k++)

        v.push_back(v1[k]);

    for (int k = j; k < v2.size(); k++)

        v.push_back(v2[k]);

    return v;

}

  
// Процедура построения дерева сегментов

void buildTree(vector<int>* tree, int* arr,

               int index, int s, int e)

{

  

    // Достигнут конечного узла

    // дерева сегментов

    if (s == e) {

        tree[index].push_back(arr[s]);

        return;

    }

  

    // Рекурсивно вызывать buildTree

    // на обоих узлах дерева

    int mid = (s + e) / 2;

    buildTree(tree, arr, 2 * index, s, mid);

    buildTree(tree, arr, 2 * index + 1, mid + 1, e);

  

    // Сохранение итогового вектора после слияния

    // два его отсортированного дочернего вектора

    tree[index] = merge(tree[2 * index], tree[2 * index + 1]);

}

  
// Процедура запроса для получения ответа
// для каждого запроса l и r - диапазон запроса

int query(vector<int>* tree, int index, int s,

          int e, int l, int r, int k)

{

  

    // вне границы или без перекрытия

    if (r < s || l > e)

        return 0;

  

    // полное перекрытие

    // Диапазон запроса полностью лежит в

    // диапазон узлов дерева сегментов

    if (s >= l && e <= r) {

        // бинарный поиск для поиска индекса k

        return (tree[index].size()

                - (lower_bound(tree[index].begin(),

                               tree[index].end(), k)

                   - tree[index].begin()));

    }

  

    // Частичное перекрытие

    // Диапазон запроса частично лежит в

    // диапазон узлов дерева сегментов

    int mid = (s + e) / 2;

    return (query(tree, 2 * index, s,

                  mid, l, r, k)

            + query(tree, 2 * index + 1, mid + 1,

                    e, l, r, k));

}

  
// Функция для выполнения запросов

void performQueries(int L[], int R[], int K[],

                    int n, int q, vector<int> tree[])

{

    for (int i = 0; i < q; i++) {

        cout << query(tree, 1, 0, n - 1,

                      L[i] - 1, R[i] - 1, K[i])

             << endl;

    }

}

  
// Код драйвера

int main()

{

    int arr[] = { 7, 3, 9, 13, 5, 4 };

    int n = sizeof(arr) / sizeof(arr[0]);

    vector<int> tree[4 * n + 1];

    buildTree(tree, arr, 1, 0, n - 1);

  

    // индексирование на основе 1

    int L[] = { 1, 2 };

    int R[] = { 4, 6 };

    int K[] = { 6, 8 };

  

    // Количество запросов

    int q = sizeof(L) / sizeof(L[0]);

  

    performQueries(L, R, K, n, q, tree);

  

    return 0;

}

Выход:

3
2

Рекомендуемые посты:

Запросы для элементов больше K в заданном диапазоне индекса с использованием дерева сегментов

0.00 (0%) 0 votes