Дерево диапазонов: логарифм в квадрате на запрос и каскадирование

Коротко

Дерево диапазонов отвечает на прямоугольный запрос за O(log² n + k) - без корня из n. Устройство: сбалансированное дерево по x, и в каждом узле - все точки его поддерева, отсортированные по y. Запрос по x раскладывается на O(log n) канонических узлов, чьи поддеревья целиком внутри по x, и в каждом двоичный поиск по y. Плата - память: каждая точка хранится на каждом уровне, всего n · log n. Частичное каскадирование убирает второй логарифм: двоичные поиски по y (для y1 и для y2) делаются только в корне, а в дочерних списках положение находится по ссылкам. Итого O(log n + k).

Если ты знаешь, как устроено дерево диапазонов, что такое канонические узлы, откуда n log n памяти и что даёт частичное каскадирование, листай до «Теперь сам».

Как думаешь, можно ли без корня

kd-дерево платит √n за каждую ячейку, которую задевает сторона прямоугольника: на миллионе точек это тысяча узлов даже для пустой полосы. Хочется логарифм, как на прямой.

Ответь себе до чтения: что, если решить задачу «по x» одной структурой, а «по y» - другой, вложенной в первую? Сколько памяти за это придётся отдать? Ответ урока: логарифм в квадрате на запрос и памяти в log n раз больше, чем точек. На 1024 точках полоса стоит 22 шага поиска вместо 62 узлов kd-дерева.

На что это похоже

Телефонный справочник города, разбитый на тома по фамилиям, а внутри каждого тома - отдельный указатель по улицам. Чтобы найти всех с фамилией на «К-М», живущих на улицах на «Л», берёшь тома «К-М» и в каждом смотришь указатель улиц. Справочник занимает больше места - улицы перечислены в каждом томе заново, - зато поиск по двум признакам идёт двумя поисками, а не листанием.

Механизм: дерево по x, списки по y

Построение. Точки сортируются по x. Над ними сбалансированное дерево: узел отвечает за отрезок точек в порядке x и хранит их y по возрастанию. Список узла - слияние списков детей, как в сортировке слиянием, поэтому построение стоит O(n · log n). Каждая точка попадает в списки всех своих предков - log n + 1 раз, отсюда память n · (log n + 1).

Запрос [x1, x2] × [y1, y2]. Двоичным поиском по x найти номера точек i1 … i2 − 1: i1 - первый x >= x1, i2 - первый x > x2 (при целых координатах - первый x >= x2 + 1, так в программах ниже). Этот отрезок номеров раскладывается на O(log n) канонических узлов - как отрезок в дереве отрезков из главы о запросах на отрезке. В каждом каноническом узле все точки подходят по x, остаётся посчитать, сколько у них y в [y1, y2], - два двоичных поиска по его списку. O(log n) узлов по O(log n) - отсюда log² n.

Номера 2 … 6 по x раскладываются на три канонических узла: 2-3, 4-5 и лист 6. В каждом узле список y уже отсортирован - двоичный поиск считает подходящие точки, не перебирая их.

Частичное каскадирование. Двоичный поиск y1 (и так же y2) в списках канонических узлов повторяется log n раз, хотя списки родителя и детей связаны: список ребёнка - часть списка родителя. Если для каждого элемента списка родителя хранить, где в списке каждого ребёнка первый элемент не меньше него, то после одного поиска в корне позиции в детях находятся по ссылке за O(1) (для позиции «за концом списка» ссылка - тоже «за концом»). Запрос - O(log n + k) при той же памяти n · log n. Приём общий: им ускоряют любые цепочки двоичных поисков по связанным спискам.

Правило

Дерево диапазонов - дерево по x, в каждом узле точки поддерева по y. Запрос раскладывается на O(log n) канонических узлов, в каждом двоичный поиск по y: O(log² n + k), с частичным каскадированием O(log n + k). Память O(n · log n), построение слиянием O(n · log n). В d измерениях - O(logᵈ n + k) на запрос и O(n · logᵈ⁻¹ n) памяти.

Разбор: те же 1024 точки и те же запросы

Точки и запросы - из прошлого урока. Считаем ответ деревом диапазонов и перебором, печатаем число канонических узлов и шагов двоичного поиска.

import random
schet = [0]

def pervyj_ne_menshe(a, x):
    lo = 0
    hi = len(a)
    while lo < hi:
        schet[0] = schet[0] + 1
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

def postroit(ys, lo, hi):
    # узел отвечает за точки lo..hi-1 в порядке x и хранит их y по
    # возрастанию: [lo, hi, левое, правое, y по возрастанию]
    if hi - lo == 1:
        return [lo, hi, None, None, [ys[lo]]]
    mid = (lo + hi) // 2
    l = postroit(ys, lo, mid)
    r = postroit(ys, mid, hi)
    a = l[4]
    b = r[4]
    slito = []
    i = 0
    j = 0
    while i < len(a) or j < len(b):
        if j == len(b) or (i < len(a) and a[i] <= b[j]):
            slito.append(a[i])
            i = i + 1
        else:
            slito.append(b[j])
            j = j + 1
    return [lo, hi, l, r, slito]

def schitat(uzel, i1, i2, y1, y2, uzlov):
    # сколько точек с номерами из [i1, i2) и y из [y1, y2]
    lo, hi, l, r, spisok = uzel
    if i2 <= lo or hi <= i1:
        return 0
    if i1 <= lo and hi <= i2:
        # канонический узел: весь его отрезок внутри - два поиска по y
        uzlov[0] = uzlov[0] + 1
        a = pervyj_ne_menshe(spisok, y1)
        return pervyj_ne_menshe(spisok, y2 + 1) - a
    a = schitat(l, i1, i2, y1, y2, uzlov)
    return a + schitat(r, i1, i2, y1, y2, uzlov)

def pamyat(uzel):
    if uzel == None:
        return 0
    return len(uzel[4]) + pamyat(uzel[2]) + pamyat(uzel[3])
random.seed(6)
tochki = []
for i in range(1024):
    tochki.append([random.randint(0, 10000), random.randint(0, 10000)])
tochki.sort()
xs = []
ys = []
for p in tochki:
    xs.append(p[0])
    ys.append(p[1])
derevo = postroit(ys, 0, len(tochki))
print(len(tochki), pamyat(derevo))
zaprosy = [[4000, 5000, 4000, 5000], [5000, 5010, 0, 10000],
           [0, 10000, 5000, 5010], [0, 10000, 0, 10000]]
for x1, x2, y1, y2 in zaprosy:
    schet[0] = 0
    uzlov = [0]
    i1 = pervyj_ne_menshe(xs, x1)
    i2 = pervyj_ne_menshe(xs, x2 + 1)
    k = schitat(derevo, i1, i2, y1, y2, uzlov)
    perebor = 0
    for p in tochki:
        if x1 <= p[0] <= x2 and y1 <= p[1] <= y2:
            perebor = perebor + 1
    print([x1, x2, y1, y2], k, perebor, uzlov[0], schet[0])

1024 11264
[4000, 5000, 4000, 5000] 10 10 5 58
[5000, 5010, 0, 10000] 1 1 1 22
[0, 10000, 5000, 5010] 1 1 1 41
[0, 10000, 0, 10000] 1024 1024 1 42

Память 11 264 = 1024 · 11 - столько значений во всех списках y: каждая точка в 11 списках (узлы и ссылки сверху). Все ответы совпали с перебором. Вертикальная полоса: один канонический узел и 22 шага поиска; у kd-дерева было 62 узла. Горизонтальная полоса: 41 шаг против 93. Весь квадрат - один канонический узел, корень, и 42 шага: подсчёт не зависит от размера ответа, тогда как kd-дерево обошло все 1024 узла.

Сравнение честное с одной оговоркой: здесь подсчёт, а kd-дерево собирало точки. Если нужен список точек, дерево диапазонов добавит k на выдачу - те же 1024 для всего квадрата. Для выдачи список узла хранит не одни y, а точки или их номера, отсортированные по y: по одному y точку не восстановить.

Разбор: как растут память и запрос

Три размера, по двадцать случайных прямоугольников. Печатаем память, среднее число канонических узлов, средние шаги поиска и log² n для сравнения.

import random
schet = [0]

def pervyj_ne_menshe(a, x):
    lo = 0
    hi = len(a)
    while lo < hi:
        schet[0] = schet[0] + 1
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

def postroit(ys, lo, hi):
    # узел отвечает за точки lo..hi-1 в порядке x и хранит их y по
    # возрастанию: [lo, hi, левое, правое, y по возрастанию]
    if hi - lo == 1:
        return [lo, hi, None, None, [ys[lo]]]
    mid = (lo + hi) // 2
    l = postroit(ys, lo, mid)
    r = postroit(ys, mid, hi)
    a = l[4]
    b = r[4]
    slito = []
    i = 0
    j = 0
    while i < len(a) or j < len(b):
        if j == len(b) or (i < len(a) and a[i] <= b[j]):
            slito.append(a[i])
            i = i + 1
        else:
            slito.append(b[j])
            j = j + 1
    return [lo, hi, l, r, slito]

def schitat(uzel, i1, i2, y1, y2, uzlov):
    # сколько точек с номерами из [i1, i2) и y из [y1, y2]
    lo, hi, l, r, spisok = uzel
    if i2 <= lo or hi <= i1:
        return 0
    if i1 <= lo and hi <= i2:
        # канонический узел: весь его отрезок внутри - два поиска по y
        uzlov[0] = uzlov[0] + 1
        a = pervyj_ne_menshe(spisok, y1)
        return pervyj_ne_menshe(spisok, y2 + 1) - a
    a = schitat(l, i1, i2, y1, y2, uzlov)
    return a + schitat(r, i1, i2, y1, y2, uzlov)

def pamyat(uzel):
    if uzel == None:
        return 0
    return len(uzel[4]) + pamyat(uzel[2]) + pamyat(uzel[3])
import math
random.seed(7)
for n in [128, 512, 2048]:
    tochki = []
    for i in range(n):
        x = random.randint(0, 10 ** 6)
        tochki.append([x, random.randint(0, 10 ** 6)])
    tochki.sort()
    xs = []
    ys = []
    for p in tochki:
        xs.append(p[0])
        ys.append(p[1])
    derevo = postroit(ys, 0, n)
    schet[0] = 0
    uzlov = [0]
    for t in range(20):
        x1 = random.randint(0, 10 ** 6)
        y1 = random.randint(0, 10 ** 6)
        x2 = x1 + random.randint(0, 3 * 10 ** 5)
        y2 = y1 + random.randint(0, 3 * 10 ** 5)
        i1 = pervyj_ne_menshe(xs, x1)
        i2 = pervyj_ne_menshe(xs, x2 + 1)
        schitat(derevo, i1, i2, y1, y2, uzlov)
    lg = math.log2(n)
    print(n, pamyat(derevo), uzlov[0] / 20, schet[0] / 20,
          round(lg * lg))

128 1024 4.35 32.7 49
512 5120 5.9 50.95 81
2048 24576 6.85 70.6 121

Память растёт как n · (log n + 1): 1024, 5120, 24 576 - при n в 16 раз больше память в 24 раза больше. Шаги запроса: 33, 51, 71 - рост как у log² n (49, 81, 121) с множителем около 0,6. Канонических узлов от четырёх до семи - логарифм.

Граница применимости - память и изменения. n · log n на миллионе точек - двадцать миллионов записей, а вставка точки требует перестроить списки на всём пути. Поэтому для изменяющихся данных берут kd-деревья и R-деревья, а дерево диапазонов - для статичных данных с огромным потоком запросов.

Что ломается без этого

Пересчитывать списки по y в каждом запросе. Это и есть перебор. Списки готовятся один раз при построении, иначе дерево по x ничего не даёт.

Сортировать каждый список заново, а не сливать. Построение становится n · log² n вместо n · log n.

Равные x у разных точек. Дерево делит точки по НОМЕРАМ в порядке x, а не по значению медианы. Если разрезать по значению «левее m - налево, правее - направо», точки с x = m окажутся неизвестно где, и запрос с границей x1 = m потеряет часть из них. Номера этого не допускают: равные x стоят подряд, и двоичный поиск отрезает их целиком.

Зачем это в работе

Аналитика по статичным данным: «сколько заказов с суммой от … до … в интервале дат», когда запросов тысячи в секунду, а данные обновляются раз в сутки. Олимпиадное программирование знает ту же структуру под именем «дерево отрезков с отсортированными списками» (merge sort tree). Частичное каскадирование используется в вычислительной геометрии повсюду: в локализации точки, в поиске по нескольким упорядоченным спискам сразу.

Теперь сам

Сколько записей займёт дерево диапазонов на 2¹⁶ = 65 536 точках?
Отрезок номеров от 3 до 12 в дереве над 16 точками. Какие канонические узлы?
Почему частичное каскадирование не помогает kd-дереву?

Ответ. 1. 65 536 · (16 + 1) = 1 114 112.

Лист 3, узел 4-7, узел 8-11, лист 12 - четыре узла.
В kd-дереве нет цепочки двоичных поисков по связанным спискам: цена складывается из ячеек, которые задевает прямоугольник, и её задаёт геометрия разбиения, а не поиск внутри узла.

Главное

Дерево диапазонов вкладывает поиск по y в каждый узел дерева по x: запрос - логарифм канонических узлов по логарифму на каждый, без корня из n. Платят памятью n · log n, а частичное каскадирование снимает и второй логарифм.