Сжатие координат в дереве Фенвика

Question

Допустим, у нас есть n пустых коробок подряд. Мы собираемся положить m групп монет в несколько последовательных коробок, которые известны заранее. Мы помещаем 1-ю группу монет в коробки от i_1 до j_1, 2-ю группу в коробки от i_2 до j_2 и так далее.

Позвольте быть c_i количество монет в коробке i, после помещения всех монет в коробки. Мы хотим, чтобы можно было быстро определить, сколько монет в коробках с индексами i = s, s + 1,... e - 1, e, т.е. мы хотим вычислить сумму

c_s +c_(s+1) + ... + c_e

эффективно. Это можно сделать с помощью дерева Фенвика. Без каких-либо улучшений дереву Фенвика требуется пространство O(n) для хранения c_i(в таблице; фактически, дерево [i]!= C_i, значения сохраняются умнее) и время O(log n) для вычисления верхней суммы.

Если у нас есть случай, когда

• n слишком велик, чтобы мы могли составить таблицу длины n (скажем, ~ 10 000 000 000)
• м достаточно мало (скажем, ~ 500 000)

есть способ как-то сжимать координаты (индексы) блоков, то есть достаточно хранить только блоки с индексами i_1, i_2,..., i_m. Поскольку значение, хранящееся в дереве [i], зависит от двоичного представления i, моя идея состоит в том, чтобы отсортировать индексы i_1, j_1, i_2, j_2,..., i_m, j_m и создать дерево длиной O (m). Добавление нового значения в дерево будет простым. Кроме того, чтобы вычислить эту сумму, нам нужно только найти первый индекс, который не больше, чем e, и последний, который не меньше, чем s. И то, и другое можно сделать с помощью бинарного поиска. После этого сумма может быть легко вычислена.

Проблема возникает в 2D случае. Теперь у нас есть область точек (x,y) на плоскости, 0 . В этой области есть m прямоугольников. Мы знаем координаты их нижнего левого и правого углов и хотим вычислить, сколько прямоугольников содержат точку (a, b). Самая простая (и моя единственная) идея - следовать манере из одномерного случая: для каждой координаты x_i углов сохраните все координаты y_i углов. Идея не такая умная, поскольку ей нужно O (m ^ 2) = слишком много места. Мой вопрос

How to store coordinates in the tree in a more efficient way?

Решения проблемы, использующие деревья Фенвика, являются предпочтительными, но любое решение приветствуется!

Answer 1

1. Самый простой подход - использовать map / unordered_map вместо 2d-массива. В этом случае вам даже не нужно сжатие координат. Карта создаст пару ключ-значение только тогда, когда это необходимо, поэтому она создает log^2(n) пар ключ-значение для каждой точки ввода.
2. Также вы можете сегментировать дерево на основе указателей (вместо массивов) с отложенной инициализацией (вы должны создавать узел только тогда, когда это необходимо).
3. Используйте 2d Segment Tree. Можно заметить, что для каждого канонического сегмента по y-координате вы можете построить дерево сегментов (1d) для x-координат только для точек, лежащих в зоне y_min <= y