Модуль 20 ⏱ ~28 мин чтения 📐 1 Mermaid диаграмм

3. Sparse table

Разреженная таблица

«Когда ваши данные высечены в камне, вычислять что-либо во время исполнения — уступка собственной лени. Предвычислите степени двойки, накройте отрезок двумя перекрывающимися ладонями и отвечайте на запросы за один цикл обращения к памяти».
— Свободная инженерная адаптация

Введение: O(1) ценой памяти и статичности

В предыдущих главах мы подробно исследовали структуры для динамических диапазонных запросов: универсальное 1. Segment tree - дерево отрезков и компактное 2. Fenwick tree - бинарное индексное дерево. Обе структуры обеспечивают строгое время $O(\log n)$ как на чтение, так и на модификацию данных, что превосходно подходит для постоянно мутирующих коллекций.

Однако в реальной практике высоконагруженного бэкенда колоссальный объем данных носит неизменяемый (статический) характер:

  • Исторические логи временных рядов (TSDB, ClickHouse, Prometheus blocks).
  • Неизменяемые таблицы маршрутизации и топологии распределенных кластеров.
  • Геопространственные индексы и полигоны доставки.
  • Предрассчитанные финансовые котировки, квантили и аналитические витрины за закрытые отчетные периоды.

В подобных сценариях, когда соотношение чтений к записям составляет миллионы к одному ($R/W \gg 10^6$), даже микросекундная логарифмическая задержка $O(\log n)$ с ветвлениями конвейера CPU становится расточительством. Промышленной системе требуется гарантированный константный отклик:
$$O(1)$$

Именно эту архитектурную нишу закрывает Sparse Table (Разреженная таблица). Она идет на осознанный прагматичный компромисс: жертвует дополнительной оперативной памятью ($O(n \log n)$) и требует предварительного построения за $O(n \log n)$, взамен предоставляя математически строгую гарантию ответа на запрос за $O(1)$ без единого цикла и ветвления.

1. Математическая основа идемпотентности

Хранить предрассчитанные ответы для каждого возможного отрезка O(n²) памяти для миллиона элементов потребовало бы терабайты данных.

Идея Sparse Table элегантна: мы вычисляем и сохраняем результаты только для отрезков, чья длина является точной степенью двойки: $2^0, 2^1, 2^2, \dots, 2^{\lfloor \log_2 n \rfloor}$. Для массива длины n существует n * log₂n таких диапазонов.

Запрос к произвольному отрезку [L, R] длины len = R - L + 1 разбивается на два предвычисленных блока размера $2^k$, где k = floor(log₂(len)) (используется логарифм log₂):

  • Первый блок начинается в L.
  • Второй блок заканчивается в R.

Так как $2^k > \text{len} / 2$, эти два блока гарантированно соприкасаются или перекрываются в середине отрезка, при этом ни на один элемент не выходя за его внешние границы [L, R]!

flowchart TD
    Range["Исходный запрос [L..R]<br/>Длина len = R - L + 1"] --> Calc["Вычисление k = floor(log2(len)) за 1 такт CPU"]

    Calc --> B1["Блок A: начало в L<br/>Длина 2^k"]
    Calc --> B2["Блок B: конец в R<br/>Длина 2^k"]

    B1 --> Overlap["Пересечение блоков<br/>f(x, x) = x (Идемпотентность)"]
    B2 --> Overlap

    Overlap --> Merge["Результат: merge(A, B)<br/>O(1) без циклов"]
    Merge --> Res["Итоговое значение RMQ"]

    classDef queryBox fill:#0f172a,stroke:#38bdf8,stroke-width:2px,color:#f8fafc;
    classDef calcBox fill:#1e293b,stroke:#f59e0b,stroke-width:1.5px,color:#f8fafc;
    classDef blockBox fill:#312e81,stroke:#818cf8,stroke-width:1.5px,color:#f8fafc;
    classDef overlapBox fill:#1e293b,stroke:#10b981,stroke-width:2px,color:#f8fafc;
    classDef resBox fill:#064e3b,stroke:#34d399,stroke-width:2px,color:#f8fafc;

    class Range queryBox;
    class Calc calcBox;
    class B1,B2 blockBox;
    class Overlap overlapBox;
    class Merge,Res resBox;

Поскольку операция идемпотентна ($x \oplus x = x$), учет элементов из зоны пересечения дважды абсолютно не искажает финальный результат:
$$\min([a, b, c, d]) = \min(\min([a, b, c]), \, \min([b, c, d]))$$

2. Production-реализация на Go 1.21+

В академических учебниках Sparse Table часто оформляют как двумерный срез [][]T. В высоконагруженном бэкенде это архитектурная ошибка: logN независимых срезов порождают logN отдельных аллокаций в куче, фрагментируют память и превращают чтение в двойное разыменование указателей (table[k][i]).

В промышленном коде мы применяем монолитный плоский массив []T с плотной упаковкой уровней по смещению offset = n * k:

Go 
package sparse

import "math/bits"

// SparseTable реализует статический диапазонный запрос (RMQ) за строгое O(1).
// Требует идемпотентную функцию merge (min, max, gcd, bitwise AND/OR).
// Хранит данные в плоском монолитном массиве для максимальной кэш-локальности.
type SparseTable[T comparable] struct {
    data  []T
    n     int
    logN  int
    merge func(a, b T) T
}

// New строит разреженную таблицу за O(n log n).
func New[T comparable](arr []T, merge func(a, b T) T) *SparseTable[T] {
    n := len(arr)
    if n == 0 {
        return &SparseTable[T]{merge: merge}
    }

    // logN = floor(log2(n)) + 1
    logN := bits.Len64(uint64(n))

    // Выделяем единый плоский непрерывный массив n * (logN + 1)
    // Уровень k хранится со смещением n * k
    table := make([]T, n*(logN+1))

    // Базовый уровень k = 0: исходные элементы массива
    for i, v := range arr {
        table[i] = v
    }

    // Заполняем уровни k = 1..logN методом динамического программирования
    for k := 1; k < logN+1; k++ {
        half := 1 << (k - 1)
        limit := n - (1 << k) + 1
        offset := n * k
        prevOffset := n * (k - 1)

        for i := 0; i < limit; i++ {
            a := table[prevOffset+i]
            b := table[prevOffset+i+half]
            table[offset+i] = merge(a, b)
        }
    }

    return &SparseTable[T]{
        data:  table,
        n:     n,
        logN:  logN,
        merge: merge,
    }
}

// Query возвращает результат на закрытом интервале [l, r] за безусловное O(1).
func (st *SparseTable[T]) Query(l, r int) T {
    if l > r || r >= st.n {
        var zero T
        return zero
    }

    length := r - l + 1
    k := bits.Len64(uint64(length)) - 1

    // Вычисление смещений в плоском массиве без ветвлений
    offset := st.n * k
    val1 := st.data[offset+l]
    val2 := st.data[offset+(r-(1<<k)+1)]

    return st.merge(val1, val2)
}

Пример использования: Мониторинг минимальной задержки

Go 
func ExampleSparseTable() {
    // Исторический массив задержек сетевых пакетов (мс)
    latencies := []int{120, 45, 800, 12, 300, 90}

    st := sparse.New(latencies, func(a, b int) int {
        if a < b {
            return a
        }
        return b
    })

    // Поиск минимума на отрезке индексов [1, 4] -> min(45, 800, 12, 300) = 12
    minVal := st.Query(1, 4)
    _ = minVal
}

3. Mechanical Sympathy: кэш, CPU и GC

То, как структура данных взаимодействует с процессорным конвейером и многоуровневым кэшем памяти, определяет реальную задержку под нагрузкой.

Плотность памяти и Cache Locality

Плоский срез []T гарантирует размещение всех уровней таблицы в монолитном блоке RAM. При вызове Query ядро процессора вычисляет два индекса и подгружает данные для val1 и val2 в кэш-линию.

Поскольку для n=10⁶ глубина k ≤ 19, для компактных типов данных (int32):
$$10^6 \times 19 \times 4\text{ байта} \approx 76\text{ МБ}$$

Это полностью умещается в разделяемый кэш третьего уровня (L3) современных серверных процессоров (AMD EPYC с 3D V-Cache до 768 МБ или Intel Xeon с 100+ МБ L3). Обращение к данным обслуживается за 15–30 нс. Если бы мы использовали фрагментированный [][]T, каждый уровень table[k] располагался бы в случайной странице кучи, провоцируя промахи TLB и задержки DRAM в 80–120 нс на каждый запрос. Уровни с малым k находятся в начале массива.

Ветвления и конвейер

Код функции Query абсолютно прямолинеен:

  • Нет циклов for.
  • Нет рекурсивных вызовов со стековыми фреймами.
  • Нет условий if, кроме начальной защиты от выхода за границы среза.

Конвейер CPU работает на максимальной пропускной способности, предвыборка инструкций не сбрасывается, а Branch Predictor угадывает переходы со 100% точностью. Сама логика выборки занимает всего 2–5 наносекунд процессорного времени!

Escape Analysis и давление на GC

При инициализации таблицы вызов make([]T, n*(logN+1)) создает ровно одну крупную аллокацию в куче.

Сборщик мусора Go аллоцирует для нее непрерывный спан страниц памяти. На фазе разметки mark GC сканирует этот блок за один последовательный проход с применением векторизованных инструкций, а при использовании примитивных типов (int, float64) срез помечается флагом noscan и вовсе игнорируется трассировщиком.

После инициализации таблица работает исключительно в режиме чтения, что позволяет безопасно разделять ее между сотнями горутин через sync.Map или обычный указатель без каких-либо блокировок и мьютексов.

4. Ограничения и архитектурные компромиссы

Разреженная таблица не является универсальным решением. Ее применение строго ограничено фундаментальными свойствами операции:

Параметр Sparse Table Segment Tree Массив + линейный проход
Запрос $O(1)$ $O(\log n)$ $O(n)$
Обновление $O(n \log n)$ полная перестройка $O(\log n)$ $O(1)$ точечная замена
Расход памяти $O(n \log n)$ $O(2 \cdot \text{nextPow2}(n))$ $O(n)$
Поддерживаемые операции Только идемпотентные Любые моноиды Любые
Сложность кода Низкая (линейный код) Средняя (дерево) Минимальная

Когда Sparse Table категорически НЕ подходит:

  1. Часто изменяемые данные: Любая точечная модификация требует полной пересборки структуры за $O(n \log n)$, что заблокирует сервис при записи.
  2. Неидемпотентные операции: Сумма, произведение, среднее арифметическое. Если сложить два перекрывающихся блока, элементы пересечения будут учтены дважды, разрушив математическую корректность.
  3. Ограниченная оперативная память: Для n=10⁷ и int64 таблица займет $\sim 1.6\text{ ГБ}$ RAM.
  4. Динамический размер: Добавление элементов в конец требует полного пересоздания буфера.

Альтернативы в Go-бэкенде:

5. Ловушки и хардкор-собеседования

Итог

  • Sparse Table — бескомпромиссный выбор для статических неизменяемых массивов и идемпотентных операций (min, max, gcd, bitwise AND/OR), обеспечивающий строгий отклик $O(1)$ на диапазонные запросы.
  • Плоский срез []T в Go устраняет разыменование указателей, снижает фрагментацию кучи и гарантирует идеальное аппаратное попадание в L3 кэш процессора.
  • Аппаратные интринзики: вызов math/bits.Len64 компилируется в инструкции LZCNT/CLZ, вычисляя логарифм за 1 такт конвейера.
  • Архитектурный компромисс: структура непригодна для частых записей ($O(n \log n)$ на перестройку) и не поддерживает неидемпотентные агрегации (суммы).
  • Для неизменяемых наборов данных разреженная таблица не требует мьютексов и обеспечивает линейное масштабирование параллельного чтения на любых многоядерных серверах.

Освоив сверхбыструю статическую агрегацию, мы переходим к фундаментальной задаче управления динамическими связными множествами и компонентами связности в распределенных графах и транзакционных системах. В следующей статье мы изучим структуру, время работы которой на практике неотличимо от чистой константы:
4. Disjoint set union DSU, Union Find.