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

Розріджена таблиця — це структура даних, яка дозволяє відповідати на запити на відрізках. Вона може відповідати на більшість запитів на відрізках за $O(\log n)$, але її справжня сила — у відповідях на запити мінімуму на відрізку (або еквівалентні запити максимуму на відрізку). Для таких запитів вона обчислює відповідь за $O(1)$.

Єдиний недолік цієї структури даних — її можна використовувати лише на незмінних масивах. Це означає, що масив не можна змінювати між двома запитами. Якщо хоч один елемент масиву змінюється, всю структуру даних доводиться перераховувати наново.

Коли підходить цей алгоритм?

• Чи масив незмінний між запитами (немає оновлень елементів)? (якщо потрібні оновлення → дерево відрізків або дерево Фенвіка)
• Чи це ідемпотентна операція (на кшталт $\min$/$\max$/$\gcd$), для якої потрібна відповідь за $O(1)$ при перекритті відрізків?
• Якщо операція не ідемпотентна (наприклад, сума), чи влаштовує відповідь за $O(\log n)$, або ж потрібна $O(1)$ для асоціативної операції? (для $O(1)$ → Sqrt-дерево)

Інтуїція

Будь-яке невід'ємне число можна однозначно подати як суму спадних степенів двійки. Це просто варіант двійкового представлення числа. Наприклад, $13 = (1101)_2 = 8 + 4 + 1$. Для числа $x$ буде щонайбільше $\lceil \log_2 x \rceil$ доданків.

За тими ж міркуваннями будь-який інтервал можна однозначно подати як об'єднання інтервалів, довжини яких є спадними степенями двійки. Наприклад, $[2, 14] = [2, 9] \cup [10, 13] \cup [14, 14]$, де весь інтервал має довжину 13, а окремі інтервали мають довжини 8, 4 і 1 відповідно. І тут також об'єднання складається щонайбільше з $\lceil \log_2(\text{довжина інтервалу}) \rceil$ інтервалів.

Основна ідея розріджених таблиць — заздалегідь обчислити всі відповіді для запитів на відрізках, довжина яких є степенем двійки. Після цього інший запит на відрізку можна обробити, розбивши відрізок на відрізки з довжинами-степенями двійки, звернувшись до попередньо обчислених відповідей і скомбінувавши їх, щоб отримати повну відповідь.

Попередні обчислення

Для зберігання відповідей на попередньо обчислені запити ми використаємо двовимірний масив. $\text{st}[i][j]$ зберігатиме відповідь для відрізка $[j, j + 2^i - 1]$ довжини $2^i$. Розмір двовимірного масиву буде $(K + 1) \times \text{MAXN}$, де $\text{MAXN}$ — найбільша можлива довжина масиву. $\text{K}$ має задовольняти $\text{K} \ge \lfloor \log_2 \text{MAXN} \rfloor$, бо $2^{\lfloor \log_2 \text{MAXN} \rfloor}$ — найбільший відрізок-степінь двійки, який нам потрібно підтримувати. Для масивів розумної довжини ($\le 10^7$ елементів) $K = 25$ — хороше значення.

Вимір $\text{MAXN}$ стоїть другим, щоб дозволити (дружні до кешу) послідовні звернення до пам'яті.

C++

int st[K + 1][MAXN];

Python

# st[i][j] зберігає відповідь для відрізка [j, j + 2**i - 1]
st = [[0] * MAXN for _ in range(K + 1)]

TypeScript

// st[i][j] зберігає відповідь для відрізка [j, j + 2**i - 1]
const st: number[][] = Array.from({ length: K + 1 }, () => new Array(MAXN).fill(0));

Go

// st[i][j] зберігає відповідь для відрізка [j, j + 2**i - 1]
var st [K + 1][MAXN]int

Оскільки відрізок $[j, j + 2^i - 1]$ довжини $2^i$ гарно розбивається на відрізки $[j, j + 2^{i - 1} - 1]$ та $[j + 2^{i - 1}, j + 2^i - 1]$, обидва довжини $2^{i - 1}$, ми можемо ефективно згенерувати таблицю за допомогою динамічного програмування:

C++

std::copy(array.begin(), array.end(), st[0]);

for (int i = 1; i <= K; i++)
    for (int j = 0; j + (1 << i) <= N; j++)
        st[i][j] = f(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);

Python

st[0][:N] = array

for i in range(1, K + 1):
    j = 0
    while j + (1 << i) <= N:
        st[i][j] = f(st[i - 1][j], st[i - 1][j + (1 << (i - 1))])
        j += 1

TypeScript

for (let j = 0; j < N; j++) st[0][j] = array[j];

for (let i = 1; i <= K; i++)
  for (let j = 0; j + (1 << i) <= N; j++)
    st[i][j] = f(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);

Go

copy(st[0][:], array)

for i := 1; i <= K; i++ {
    for j := 0; j+(1<<i) <= N; j++ {
        st[i][j] = f(st[i-1][j], st[i-1][j+(1<<(i-1))])
    }
}

Функція $f$ залежатиме від типу запиту. Для запитів суми на відрізку вона обчислюватиме суму, для запитів мінімуму на відрізку — мінімум.

Часова складність попередніх обчислень становить $O(\text{N} \log \text{N})$.

Запити суми на відрізку

Для цього типу запитів ми хочемо знайти суму всіх значень на відрізку. Тому природним означенням функції $f$ є $f(x, y) = x + y$. Ми можемо побудувати структуру даних так:

C++

long long st[K + 1][MAXN];

std::copy(array.begin(), array.end(), st[0]);

for (int i = 1; i <= K; i++)
    for (int j = 0; j + (1 << i) <= N; j++)
        st[i][j] = st[i - 1][j] + st[i - 1][j + (1 << (i - 1))];

Python

st = [[0] * MAXN for _ in range(K + 1)]
st[0][:N] = array

for i in range(1, K + 1):
    j = 0
    while j + (1 << i) <= N:
        st[i][j] = st[i - 1][j] + st[i - 1][j + (1 << (i - 1))]
        j += 1

TypeScript

// сума може перевищити 2**53 — використовуємо bigint
const st: bigint[][] = Array.from({ length: K + 1 }, () => new Array(MAXN).fill(0n));
for (let j = 0; j < N; j++) st[0][j] = BigInt(array[j]);

for (let i = 1; i <= K; i++)
  for (let j = 0; j + (1 << i) <= N; j++)
    st[i][j] = st[i - 1][j] + st[i - 1][j + (1 << (i - 1))];

Go

var st [K + 1][MAXN]int64

for j := 0; j < N; j++ {
    st[0][j] = int64(array[j])
}

for i := 1; i <= K; i++ {
    for j := 0; j+(1<<i) <= N; j++ {
        st[i][j] = st[i-1][j] + st[i-1][j+(1<<(i-1))]
    }
}

Щоб відповісти на запит суми для відрізка $[L, R]$, ми перебираємо всі степені двійки, починаючи з найбільшого. Щойно степінь двійки $2^i$ стає меншим або рівним за довжину відрізка ($= R - L + 1$), ми обробляємо першу частину відрізка $[L, L + 2^i - 1]$ і продовжуємо з рештою відрізка $[L + 2^i, R]$.

C++

long long sum = 0;
for (int i = K; i >= 0; i--) {
    if ((1 << i) <= R - L + 1) {
        sum += st[i][L];
        L += 1 << i;
    }
}

Python

total = 0
for i in range(K, -1, -1):
    if (1 << i) <= R - L + 1:
        total += st[i][L]
        L += 1 << i

TypeScript

let sum = 0n;
for (let i = K; i >= 0; i--) {
  if (1 << i <= R - L + 1) {
    sum += st[i][L];
    L += 1 << i;
  }
}

Go

var sum int64 = 0
for i := K; i >= 0; i-- {
    if (1 << i) <= R-L+1 {
        sum += st[i][L]
        L += 1 << i
    }
}

Часова складність запиту суми на відрізку становить $O(K) = O(\log \text{MAXN})$.

Запити мінімуму на відрізку (RMQ)

Це ті запити, у яких розріджена таблиця сяє. Під час обчислення мінімуму на відрізку немає значення, чи обробляємо ми значення з відрізка один раз чи двічі. Тому замість розбиття відрізка на кілька відрізків ми можемо розбити його лише на два відрізки-степені двійки, що перекриваються. Наприклад, ми можемо розбити відрізок $[1, 6]$ на відрізки $[1, 4]$ та $[3, 6]$. Мінімум на відрізку $[1, 6]$ очевидно дорівнює мінімуму з мінімуму на відрізку $[1, 4]$ та мінімуму на відрізку $[3, 6]$. Отже, ми можемо обчислити мінімум на відрізку $[L, R]$ так:

$$\min(\text{st}[i][L], \text{st}[i][R - 2^i + 1]) \quad \text{ де } i = \log_2(R - L + 1)$$

Це вимагає, щоб ми вміли швидко обчислювати $\log_2(R - L + 1)$. Цього можна досягти, попередньо обчисливши всі логарифми:

C++

int lg[MAXN+1];
lg[1] = 0;
for (int i = 2; i <= MAXN; i++)
    lg[i] = lg[i/2] + 1;

Python

lg = [0] * (MAXN + 1)
for i in range(2, MAXN + 1):
    lg[i] = lg[i // 2] + 1

TypeScript

const lg = new Array(MAXN + 1).fill(0);
for (let i = 2; i <= MAXN; i++) lg[i] = lg[i >> 1] + 1;

Go

var lg [MAXN + 1]int
for i := 2; i <= MAXN; i++ {
    lg[i] = lg[i/2] + 1
}

Як альтернатива, логарифм можна обчислювати на льоту за сталий час і сталу пам'ять:

C++

// C++20
#include <bit>
int log2_floor(unsigned long i) {
    return std::bit_width(i) - 1;
}

// до C++20
int log2_floor(unsigned long long i) {
    return i ? __builtin_clzll(1) - __builtin_clzll(i) : -1;
}

Python

# int.bit_length() повертає кількість бітів числа, тож floor(log2(i)) = i.bit_length() - 1
def log2_floor(i: int) -> int:
    return i.bit_length() - 1 if i else -1

TypeScript

// Math.clz32(x) — кількість провідних нулів у 32-бітному поданні,
// тож floor(log2(i)) = 31 - Math.clz32(i)
function log2Floor(i: number): number {
  return i ? 31 - Math.clz32(i) : -1;
}

Go

import "math/bits"

// bits.Len повертає кількість значущих бітів, тож floor(log2(i)) = bits.Len(i) - 1
func log2Floor(i uint) int {
    return bits.Len(i) - 1
}

Цей замір швидкодії показує, що використання масиву lg повільніше через промахи кешу.

Після цього нам потрібно попередньо обчислити структуру розрідженої таблиці. Цього разу ми означимо $f$ як $f(x, y) = \min(x, y)$.

C++

int st[K + 1][MAXN];

std::copy(array.begin(), array.end(), st[0]);

for (int i = 1; i <= K; i++)
    for (int j = 0; j + (1 << i) <= N; j++)
        st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);

Python

st = [[0] * MAXN for _ in range(K + 1)]
st[0][:N] = array

for i in range(1, K + 1):
    j = 0
    while j + (1 << i) <= N:
        st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))])
        j += 1

TypeScript

const st: number[][] = Array.from({ length: K + 1 }, () => new Array(MAXN).fill(0));
for (let j = 0; j < N; j++) st[0][j] = array[j];

for (let i = 1; i <= K; i++)
  for (let j = 0; j + (1 << i) <= N; j++)
    st[i][j] = Math.min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);

Go

var st [K + 1][MAXN]int
copy(st[0][:], array)

for i := 1; i <= K; i++ {
    for j := 0; j+(1<<i) <= N; j++ {
        st[i][j] = min(st[i-1][j], st[i-1][j+(1<<(i-1))])
    }
}

А мінімум на відрізку $[L, R]$ можна обчислити так:

C++

int i = lg[R - L + 1];
int minimum = min(st[i][L], st[i][R - (1 << i) + 1]);

Python

i = lg[R - L + 1]
minimum = min(st[i][L], st[i][R - (1 << i) + 1])

TypeScript

const i = lg[R - L + 1];
const minimum = Math.min(st[i][L], st[i][R - (1 << i) + 1]);

Go

i := lg[R-L+1]
minimum := min(st[i][L], st[i][R-(1<<i)+1])

Часова складність запиту мінімуму на відрізку становить $O(1)$.

Подібні структури даних, що підтримують більше типів запитів

Одна з основних слабкостей підходу з $O(1)$, обговореного в попередньому розділі, полягає в тому, що цей підхід підтримує лише запити ідемпотентних функцій. Тобто він чудово працює для запитів мінімуму на відрізку, але відповісти на запити суми на відрізку цим підходом неможливо.

Існують подібні структури даних, які можуть обробляти будь-який тип асоціативних функцій і відповідати на запити на відрізках за $O(1)$. Одна з них називається Disjoint Sparse Table. Інша — це Sqrt Tree.

Задачі для практики

• SPOJ - RMQSQ
• SPOJ - THRBL
• Codechef - MSTICK
• Codechef - SEAD
• Codeforces - CGCDSSQ
• Codeforces - R2D2 and Droid Army
• Codeforces - Maximum of Maximums of Minimums
• SPOJ - Miraculous
• DevSkill - Multiplication Interval (archived)
• Codeforces - Animals and Puzzles
• Codeforces - Trains and Statistics
• SPOJ - Postering
• SPOJ - Negative Score
• SPOJ - A Famous City
• SPOJ - Diferencija
• Codeforces - Turn off the TV
• Codeforces - Map
• Codeforces - Awards for Contestants
• Codeforces - Longest Regular Bracket Sequence
• CSES - Static Range Minimum Queries
• Codeforces - Array Stabilization (GCD version)

Відеоматеріали