Насколько я понял вопрос у вас есть диапазон [A, B] и запросы вида -
- Назначить определенный диапазон категории
E.g.
R1 R2 C1
R3 R4 C2
- Запрос диапазона для общего количества элементов в определенных категориях.
Например. найти количество категорий в R1 R4
Простая реализация, использующая словари, как указано выше, не будет работать, как я описываю этим примером -
предположим, что у нас есть диапазон [1000, 5000]
и мы назначаем следующее:
1 2 C1
2 3 C2
3 4 C3
......
4999 5000 C4999
Теперь мы выполняем следующее задание
1 5000 C5555
Это сделает обновление / изменение / удаление ранее назначенных диапазонов диапазонов O (N), где N - максимальный размер диапазона (B - A)
D ['category'] = set (of_all_the_ranges_you_have_in_category)
В этом случае необходимо удалить предыдущие диапазоны из соответствующих наборов в категориях C1, C2 ... C4999 для последнего присвоения (1 5000 C5555)
OR
1: {"stop": 5, "category": "C1"},
6: {"стоп": 19, "категория": "C23"},
Здесь обновление категории для каждого начального значения (1,2,3,4 ..., 4999) потребуется для последнего назначения (1 5000 C5555)
Лучшим вариантом для обновления диапазонов в O (lg n) будут деревья сегментов.
(http://en.wikipedia.org/wiki/Segment_tree)
В приведенном выше примере дерево сегментов будет выглядеть примерно так
1000:5000
|
---------------------
| |
1000:3000 3001:5000
| |
---------------- --------------------
| | | |
1000:2000 2001:3000 3001:4000 4001:5000
............................................... ..................
.................................................. ............. и т. д.
Конечные узлы будут иметь диапазоны (1: 2, 2: 3, ...)
Вы можете присвоить значение «категория» каждому узлу и задавать интервал, пересекающий дерево, делящий интервал соответствующим образом (например, для 2500–4500, делите на 2500: 3000 и 3001: 4500 и продолжайте в обоих направлениях до узлов с совпадающими диапазонами найдены).
Теперь интересно обновлять дочерние узлы, когда они вам нужны. Например, не продолжайте обновлять детей сразу же при выполнении заданий, таких как 1 5000 C5555. Эта вещь называется ленивым распространением, и вы можете узнать больше об этом здесь (http://www.spoj.pl/forum/viewtopic.php?f=27&t=8296).
Теперь для части запроса. Если количество категорий очень мало, вы можете вести таблицу частот на каждом узле и обновлять диапазоны, когда это необходимо, и лениво распространяться, когда это необходимо, в противном случае вам придется обходить все дерево от листа к узлу, счет и сложность станут равны O (п). * * 1 056
Я думаю, что лучшее решение для запросов может существовать. Это не приходит мне в голову.
UPDATE
Давайте возьмем небольшой пример.
Диапазон [1,8]
Категории разрешены {C1, C2}
1:8
1:4 5:8
1:2 3:4 5:6 7:8
1:1 2:2 3:3 4:4 5:5 6:6 7:7 8:8
Каждый узел будет иметь 3 поля [category, category_counts [], children_update_required = false]
1 5 С1
Запрос будет разделен, и для категории узлов 1: 4 будет установлено значение C1, а для children_update_required будет установлено значение true, его дочерние элементы теперь не будут обновляться (запоминайте обновление только при необходимости или при отложенном распространении). Также категория узла 5: 5 будет установлена в C1
3 4 C2
Запрос будет распространяться по дереву в направлении 3: 4 (и в процессе достижения категорий 3: 4, 1: 2 и 3: 4 будет обновляться до C1, 1: 4 для children_update_required будет установлено значение false, 1: 2 и 3: 4 для children_update_required будет установлено в значение true) и теперь будет обновлять категорию с 3: 4 до C2 в соответствии с текущими требованиями. Затем он установит значение children_update, равное 3: 4, для истины для будущего обновления своих дочерних элементов (что уже установлено в этом случае .. без вреда).