Построение дерева сегментов

Учитывая целочисленный массив A из n элементов и m запросов, каждый запрос содержит целое число x, я должен ответить на количество элементов в массиве меньше x. 0 ‹ А[i] ‹ 10^6 && х ‹ 10^6

пример:

A[]={105,2,9,3,8,5,7,7}

запрос

6

8

104

отвечать

3

5

7

Объяснение:

для элементов query1 = {2,3,5}

для элементов query2 = {2,3,5,7,7}

для элементов query3 = {2,9,3,8,5,7,7}

Вопрос:

Как решить этот вопрос, используя дерево сегментов? (Я построил дерево сегментов для нахождения максимума, минимума и суммы в диапазоне, но мой разум становится пустым, как построить дерево сегментов для этого). Пожалуйста, объясните на примере

Примечание. Я уже знаю решение nlogn, использующее сортировку и бинарный поиск (для каждого запроса). Я хочу узнать, как можно использовать дерево сегментов для решения этой проблемы.

Спасибо


c++ algorithm data-structures segment-tree
person puja    schedule 15.02.2016    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Я не думаю, что дерево сегментов будет работать, если вы построите его для элементов массива A. Вы можете использовать некоторую эвристику/сокращение, используя максимум и минимум для сегмента, но, в конце концов, для таких случаев, как

0, 10^6, 0, 10^6, 0, 10^6,...

запросы выродятся до O(n), потому что вам нужно спускаться по каждому листу.

Что вам нужно сделать, так это построить дерево сегментов по диапазону возможных значений: для каждого значения 0<a<10^6 вы помните, сколько элементов с этим значением находится в массиве A. Например для

A=[5,2,3,3,3,5,7,7]

массив вхождений будет

f=[0,0,1,3,0,2,0,1,0,...]

Теперь запрос количества элементов в массиве A, меньшего, чем x, преобразуется в запрос суммы элементов в массиве вхождений f из 0. до x.

Вы можете использовать дерево сегментов, чтобы ответить на эти запросы.

Однако, если вы знаете весь массив до запросов — это довольно скучный случай — вы можете просто использовать префикс sum в массиве f со временем предварительной обработки O(n) и временем запроса O(1).

Деревья сегментов интересны только в том случае, если запросы и обновления массива A чередуются.

Если запросы и обновления чередуются, я бы рекомендовал использовать Fenwicktree, это не так гибко, как дерево сегментов, но оно заточено именно под такие задачи. Его проще реализовать, он быстрее и требует меньше памяти.

person ead    schedule 16.02.2016

arrow_upward
0
arrow_downward

Используя обычное дерево сегментов, невозможно ответить на этот тип запросов за O(logn). Вам нужно использовать вейвлет-дерево (есть также несколько других структур данных, которые позволяют ответить на этот запрос, но вейвлет-деревья — это самое интересное). Эти ссылки могут быть полезны, если вы не знаете эту структуру данных:

https://codeforces.com/blog/entry/52854

https://youtu.be/4aSv9PcecDw

person Rentib    schedule 05.11.2020