Sqrt-дерево

Нехай задано масив $a$ з $n$ елементів та операцію $\circ$ , що задовольняє властивість асоціативності: $(x \circ y) \circ z = x \circ (y \circ z)$ виконується для будь-яких $x$ , $y$ , $z$ .

Отже, такі операції, як $\gcd$ , $\min$ , $\max$ , $+$ , $\text{and}$ , $\text{or}$ , $\text{xor}$ тощо, задовольняють ці умови.

Також ми маємо деякі запити $q(l, r)$ . Для кожного запиту нам потрібно обчислити $a_l \circ a_{l+1} \circ \dots \circ a_r$ .

Sqrt-дерево може обробляти такі запити за $O(1)$ часу з $O(n \cdot \log \log n)$ часу на попередню обробку та $O(n \cdot \log \log n)$ пам'яті.

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

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

Опис

Побудова кореневого розбиття

Зробімо кореневе розбиття. Ми ділимо наш масив на $\sqrt{n}$ блоків, кожен блок має розмір $\sqrt{n}$ . Для кожного блоку ми обчислюємо:

Відповіді на запити, що лежать у блоці й починаються з початку блоку ( $\text{prefixOp}$ )
Відповіді на запити, що лежать у блоці й закінчуються в кінці блоку ( $\text{suffixOp}$ )

А ще ми обчислимо додатковий масив:

$\text{between}_{i, j}$ (для $i \le j$ ) — відповідь на запит, що починається на початку блоку $i$ і закінчується в кінці блоку $j$ . Зауважимо, що ми маємо $\sqrt{n}$ блоків, тож розмір цього масиву буде $O(\sqrt{n}^2) = O(n)$ .

Розгляньмо приклад.

Нехай $\circ$ — це $+$ (ми обчислюємо суму на відрізку) і ми маємо такий масив $a$ :

{1, 2, 3, 4, 5, 6, 7, 8, 9}

Він буде поділений на три блоки: {1, 2, 3}, {4, 5, 6} і {7, 8, 9}.

Для першого блоку $\text{prefixOp}$ — це {1, 3, 6}, а $\text{suffixOp}$ — це {6, 5, 3}.

Для другого блоку $\text{prefixOp}$ — це {4, 9, 15}, а $\text{suffixOp}$ — це {15, 11, 6}.

Для третього блоку $\text{prefixOp}$ — це {7, 15, 24}, а $\text{suffixOp}$ — це {24, 17, 9}.

Масив $\text{between}$ :

{
    {6, 21, 45},
    {0, 15, 39},
    {0, 0,  24}
}

(ми вважаємо, що некоректні елементи, де $i > j$ , заповнені нулями)

Очевидно, що ці масиви можна легко обчислити за $O(n)$ часу та пам'яті.

Ми вже можемо відповідати на деякі запити, використовуючи ці масиви. Якщо запит не вміщається в один блок, ми можемо поділити його на три частини: суфікс блоку, потім деякий відрізок із суміжних блоків, а далі префікс якогось блоку. Ми можемо відповісти на запит, поділивши його на три частини й узявши нашу операцію від деякого значення з $\text{suffixOp}$ , потім деякого значення з $\text{between}$ , а потім деякого значення з $\text{prefixOp}$ .

Але якщо ми маємо запити, що повністю вміщаються в один блок, ми не можемо обробити їх за допомогою цих трьох масивів. Отже, нам потрібно щось зробити.

Будуємо дерево

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

Отже, ми отримуємо дерево. Кожна вершина дерева представляє деякий відрізок масиву. Вершина, що представляє відрізок масиву розміру $k$ , має $\sqrt{k}$ дітей — по одній на кожен блок. Також кожна вершина містить три масиви, описані вище, для відрізка, який вона містить. Корінь дерева представляє весь масив. Вершини з довжинами відрізків $1$ або $2$ є листками.

Також очевидно, що висота цього дерева — $O(\log \log n)$ , тому що якщо деяка вершина дерева представляє масив довжини $k$ , то її діти мають довжину $\sqrt{k}$ . $\log(\sqrt{k}) = \frac{\log{k}}{2}$ , тож $\log k$ зменшується вдвічі на кожному шарі дерева, а отже, його висота — $O(\log \log n)$ . Час на побудову та використання пам'яті будуть $O(n \cdot \log \log n)$ , тому що кожен елемент масиву з'являється рівно один раз на кожному шарі дерева.

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

Гаразд, тепер ми можемо робити $O(\log \log n)$ на запит. Чи можна зробити це швидше?

Оптимізація складності запиту

Одна з найочевидніших оптимізацій — це бінарний пошук вершини дерева, яка нам потрібна. Використовуючи бінарний пошук, ми можемо досягти складності $O(\log \log \log n)$ на запит. Чи можемо ми зробити це ще швидше?

Відповідь — так. Припустімо такі дві речі:

Кожен розмір блоку є степенем двійки.
Усі блоки рівні на кожному шарі.

Щоб цього досягти, ми можемо додати деякі нульові елементи до нашого масиву, щоб його розмір став степенем двійки.

Коли ми це використовуємо, деякі розміри блоків можуть стати вдвічі більшими, щоб бути степенем двійки, але вони все одно будуть $O(\sqrt{k})$ за розміром, і ми зберігаємо лінійну складність для побудови масивів у відрізку.

Тепер ми можемо легко перевірити, чи вміщається запит повністю в блок розміру $2^k$ . Запишемо межі запиту, $l$ та $r$ (ми використовуємо 0-індексацію), у двійковій формі. Наприклад, припустімо $k=4, l=39, r=46$ . Двійкове представлення $l$ та $r$ :

$l = 39_{10} = 100111_2$

$r = 46_{10} = 101110_2$

Пам'ятаймо, що один шар містить відрізки рівного розміру, а блоки на одному шарі також мають рівний розмір (у нашому випадку їхній розмір — $2^k = 2^4 = 16$ ). Блоки повністю покривають масив, тож перший блок покриває елементи $(0 - 15)$ ( $(000000_2 - 001111_2)$ у двійковому вигляді), другий покриває елементи $(16 - 31)$ ( $(010000_2 - 011111_2)$ у двійковому вигляді) і так далі. Ми бачимо, що індекси позицій, покритих одним блоком, можуть відрізнятися лише в $k$ (у нашому випадку $4$ ) останніх бітах. У нашому випадку $l$ та $r$ мають рівні біти, окрім чотирьох найнижчих, тож вони лежать в одному блоці.

Отже, нам потрібно перевірити, чи відрізняється не більше ніж $k$ найменших бітів (або чи $l\ \text{xor}\ r$ не перевищує $2^k-1$ ).

Використовуючи це спостереження, ми можемо знайти шар, придатний для швидкої відповіді на запит. Як це зробити:

Для кожного $i$ , що не перевищує розмір масиву, ми знаходимо найвищий біт, рівний $1$ . Щоб зробити це швидко, ми використовуємо ДП та попередньо обчислений масив.
Тепер для кожного $q(l, r)$ ми знаходимо найвищий біт $l\ \text{xor}\ r$ і, використовуючи цю інформацію, легко обираємо шар, на якому ми можемо легко обробити запит. Тут ми також можемо використати попередньо обчислений масив.

Детальніше дивіться код нижче.

Отже, використовуючи це, ми можемо відповідати на запити за $O(1)$ кожен. Ура! :)

Оновлення елементів

Ми також можемо оновлювати елементи в sqrt-дереві. Підтримуються як оновлення окремого елемента, так і оновлення на відрізку.

Оновлення окремого елемента

Розгляньмо запит $\text{update}(x, val)$ , що виконує присвоєння $a_x = val$ . Нам потрібно виконати цей запит достатньо швидко.

Наївний підхід

Спочатку погляньмо, що змінюється в дереві, коли змінюється окремий елемент. Розгляньмо вершину дерева з довжиною $l$ та її масиви: $\text{prefixOp}$ , $\text{suffixOp}$ та $\text{between}$ . Легко бачити, що лише $O(\sqrt{l})$ елементів із $\text{prefixOp}$ та $\text{suffixOp}$ змінюються (лише всередині блоку зі зміненим елементом). $O(l)$ елементів змінюються в $\text{between}$ . Отже, $O(l)$ елементів у вершині дерева оновлюються.

Ми пам'ятаємо, що будь-який елемент $x$ присутній рівно в одній вершині дерева на кожному шарі. Коренева вершина (шар $0$ ) має довжину $O(n)$ , вершини на шарі $1$ мають довжину $O(\sqrt{n})$ , вершини на шарі $2$ мають довжину $O(\sqrt{\sqrt{n}})$ тощо. Отже, часова складність на одне оновлення — $O(n + \sqrt{n} + \sqrt{\sqrt{n}} + \dots) = O(n)$ .

Але це надто повільно. Чи можна зробити це швидше?

Sqrt-дерево всередині sqrt-дерева

Зауважимо, що вузьке місце оновлення — це перебудова $\text{between}$ кореневої вершини. Щоб оптимізувати дерево, позбудьмося цього масиву! Замість масиву $\text{between}$ ми зберігаємо для кореневої вершини інше sqrt-дерево. Назвімо його $\text{index}$ . Воно відіграє ту саму роль, що й $\text{between}$ , — відповідає на запити на відрізках блоків. Зауважимо, що решта вершин дерева не мають $\text{index}$ , вони зберігають свої масиви $\text{between}$ .

Sqrt-дерево є індексованим, якщо його коренева вершина має $\text{index}$ . Sqrt-дерево з масивом $\text{between}$ у його кореневій вершині є неіндексованим. Зауважимо, що $\text{index}$ сам є неіндексованим.

Отже, ми маємо такий алгоритм для оновлення індексованого дерева:

Оновити $\text{prefixOp}$ та $\text{suffixOp}$ за $O(\sqrt{n})$ .
Оновити $\text{index}$ . Воно має довжину $O(\sqrt{n})$ , і нам потрібно оновити в ньому лише один елемент (який представляє змінений блок). Отже, часова складність цього кроку — $O(\sqrt{n})$ . Ми можемо використати алгоритм, описаний на початку цього розділу («повільний»), щоб це зробити.
Перейти у вершину-дитину, що представляє змінений блок, і оновити її за $O(\sqrt{n})$ «повільним» алгоритмом.

Зауважимо, що складність запиту все ще $O(1)$ : нам потрібно використати $\text{index}$ у запиті не більше одного разу, і це займе $O(1)$ часу.

Отже, загальна часова складність оновлення окремого елемента — $O(\sqrt{n})$ . Ура! :)

Оновлення відрізка

Sqrt-дерево також може робити такі речі, як присвоєння елемента на відрізку. $\text{massUpdate}(x, l, r)$ означає $a_i = x$ для всіх $l \le i \le r$ .

Є два підходи, щоб це зробити: один із них робить $\text{massUpdate}$ за $O(\sqrt{n}\cdot \log \log n)$ , зберігаючи $O(1)$ на запит. Другий робить $\text{massUpdate}$ за $O(\sqrt{n})$ , але складність запиту стає $O(\log \log n)$ .

Ми будемо робити відкладені оновлення так само, як це робиться в деревах відрізків: ми позначаємо деякі вершини як відкладені (lazy), маючи на увазі, що ми проштовхнемо їх, коли це буде необхідно. Але одна річ відрізняється від дерев відрізків: проштовхування вершини є дорогим, тож його не можна виконувати в запитах. На шарі $0$ проштовхування вершини займає $O(\sqrt{n})$ часу. Отже, ми не проштовхуємо вершини всередині запитів, ми лише дивимося, чи є поточна вершина або її батько відкладеними, і просто враховуємо це під час виконання запитів.

Перший підхід

У першому підході ми кажемо, що лише вершини на шарі $1$ (з довжиною $O(\sqrt{n}$ ) можуть бути відкладеними. Коли ми проштовхуємо таку вершину, вона оновлює все своє піддерево, включно із собою, за $O(\sqrt{n}\cdot \log \log n)$ . Процес $\text{massUpdate}$ виконується так:

Розглядаємо вершини на шарі $1$ та блоки, що їм відповідають.
Деякі блоки повністю покриті $\text{massUpdate}$ . Позначаємо їх як відкладені за $O(\sqrt{n})$ .
Деякі блоки покриті частково. Зауважимо, що таких блоків не більше двох. Перебудовуємо їх за $O(\sqrt{n}\cdot \log \log n)$ . Якщо вони були відкладеними, враховуємо це.
Оновлюємо $\text{prefixOp}$ та $\text{suffixOp}$ для частково покритих блоків за $O(\sqrt{n})$ (тому що таких блоків лише два).
Перебудовуємо $\text{index}$ за $O(\sqrt{n}\cdot \log \log n)$ .

Отже, ми можемо робити $\text{massUpdate}$ швидко. Але як відкладені оновлення впливають на запити? Вони матимуть такі зміни:

Якщо наш запит повністю лежить у відкладеному блоці, обчислюємо його та враховуємо відкладеність. $O(1)$ .
Якщо наш запит складається з багатьох блоків, деякі з яких відкладені, нам потрібно подбати про відкладеність лише в найлівішому та найправішому блоці. Решта блоків обчислюється за допомогою $\text{index}$ , який уже знає відповідь на відкладеному блоці (тому що його перебудовують після кожної зміни). $O(1)$ .

Складність запиту все ще залишається $O(1)$ .

Другий підхід

У цьому підході кожна вершина може бути відкладеною (окрім кореня). Навіть вершини в $\text{index}$ можуть бути відкладеними. Отже, під час обробки запиту ми маємо шукати позначки відкладеності в усіх батьківських вершинах, тобто складність запиту буде $O(\log \log n)$ .

Але $\text{massUpdate}$ стає швидшим. Він виглядає так:

Деякі блоки повністю покриті $\text{massUpdate}$ . Отже, до них додаються позначки відкладеності. Це $O(\sqrt{n})$ .
Оновлюємо $\text{prefixOp}$ та $\text{suffixOp}$ для частково покритих блоків за $O(\sqrt{n})$ (тому що таких блоків лише два).
Не забуваємо оновити index. Це $O(\sqrt{n})$ (ми використовуємо той самий алгоритм $\text{massUpdate}$ ).
Оновлюємо масив $\text{between}$ для неіндексованих піддерев.
Заходимо у вершини, що представляють частково покриті блоки, і викликаємо $\text{massUpdate}$ рекурсивно.

Зауважимо, що коли ми робимо рекурсивний виклик, ми робимо префіксний або суфіксний $\text{massUpdate}$ . Але для префіксних та суфіксних оновлень ми можемо мати не більше однієї частково покритої дитини. Отже, ми відвідуємо одну вершину на шарі $1$ , дві вершини на шарі $2$ і дві вершини на будь-якому глибшому рівні. Тож часова складність — $O(\sqrt{n} + \sqrt{\sqrt{n}} + \dots) = O(\sqrt{n})$ . Підхід тут схожий на масове оновлення дерева відрізків.

Реалізація

Наступна реалізація sqrt-дерева може виконувати такі операції: побудова за $O(n \cdot \log \log n)$ , відповідь на запити за $O(1)$ та оновлення елемента за $O(\sqrt{n})$ .

SqrtTreeItem op(const SqrtTreeItem &a, const SqrtTreeItem &b);

inline int log2Up(int n) {
	int res = 0;
	while ((1 << res) < n) {
		res++;
	}
	return res;
}

class SqrtTree {
private:
	int n, lg, indexSz;
	vector<SqrtTreeItem> v;
	vector<int> clz, layers, onLayer;
	vector< vector<SqrtTreeItem> > pref, suf, between;
	
	inline void buildBlock(int layer, int l, int r) {
		pref[layer][l] = v[l];
		for (int i = l+1; i < r; i++) {
			pref[layer][i] = op(pref[layer][i-1], v[i]);
		}
		suf[layer][r-1] = v[r-1];
		for (int i = r-2; i >= l; i--) {
			suf[layer][i] = op(v[i], suf[layer][i+1]);
		}
	}
	
	inline void buildBetween(int layer, int lBound, int rBound, int betweenOffs) {
		int bSzLog = (layers[layer]+1) >> 1;
		int bCntLog = layers[layer] >> 1;
		int bSz = 1 << bSzLog;
		int bCnt = (rBound - lBound + bSz - 1) >> bSzLog;
		for (int i = 0; i < bCnt; i++) {
			SqrtTreeItem ans;
			for (int j = i; j < bCnt; j++) {
				SqrtTreeItem add = suf[layer][lBound + (j << bSzLog)];
				ans = (i == j) ? add : op(ans, add);
				between[layer-1][betweenOffs + lBound + (i << bCntLog) + j] = ans;
			}
		}
	}
	
	inline void buildBetweenZero() {
		int bSzLog = (lg+1) >> 1;
		for (int i = 0; i < indexSz; i++) {
			v[n+i] = suf[0][i << bSzLog];
		}
		build(1, n, n + indexSz, (1 << lg) - n);
	}
	
	inline void updateBetweenZero(int bid) {
		int bSzLog = (lg+1) >> 1;
		v[n+bid] = suf[0][bid << bSzLog];
		update(1, n, n + indexSz, (1 << lg) - n, n+bid);
	}
	
	void build(int layer, int lBound, int rBound, int betweenOffs) {
		if (layer >= (int)layers.size()) {
			return;
		}
		int bSz = 1 << ((layers[layer]+1) >> 1);
		for (int l = lBound; l < rBound; l += bSz) {
			int r = min(l + bSz, rBound);
			buildBlock(layer, l, r);
			build(layer+1, l, r, betweenOffs);
		}
		if (layer == 0) {
			buildBetweenZero();
		} else {
			buildBetween(layer, lBound, rBound, betweenOffs);
		}
	}
	
	void update(int layer, int lBound, int rBound, int betweenOffs, int x) {
		if (layer >= (int)layers.size()) {
			return;
		}
		int bSzLog = (layers[layer]+1) >> 1;
		int bSz = 1 << bSzLog;
		int blockIdx = (x - lBound) >> bSzLog;
		int l = lBound + (blockIdx << bSzLog);
		int r = min(l + bSz, rBound);
		buildBlock(layer, l, r);
		if (layer == 0) {
			updateBetweenZero(blockIdx);
		} else {
			buildBetween(layer, lBound, rBound, betweenOffs);
		}
		update(layer+1, l, r, betweenOffs, x);
	}
	
	inline SqrtTreeItem query(int l, int r, int betweenOffs, int base) {
		if (l == r) {
			return v[l];
		}
		if (l + 1 == r) {
			return op(v[l], v[r]);
		}
		int layer = onLayer[clz[(l - base) ^ (r - base)]];
		int bSzLog = (layers[layer]+1) >> 1;
		int bCntLog = layers[layer] >> 1;
		int lBound = (((l - base) >> layers[layer]) << layers[layer]) + base;
		int lBlock = ((l - lBound) >> bSzLog) + 1;
		int rBlock = ((r - lBound) >> bSzLog) - 1;
		SqrtTreeItem ans = suf[layer][l];
		if (lBlock <= rBlock) {
			SqrtTreeItem add = (layer == 0) ? (
				query(n + lBlock, n + rBlock, (1 << lg) - n, n)
			) : (
				between[layer-1][betweenOffs + lBound + (lBlock << bCntLog) + rBlock]
			);
			ans = op(ans, add);
		}
		ans = op(ans, pref[layer][r]);
		return ans;
	}
public:
	inline SqrtTreeItem query(int l, int r) {
		return query(l, r, 0, 0);
	}
	
	inline void update(int x, const SqrtTreeItem &item) {
		v[x] = item;
		update(0, 0, n, 0, x);
	}
	
	SqrtTree(const vector<SqrtTreeItem>& a)
		: n((int)a.size()), lg(log2Up(n)), v(a), clz(1 << lg), onLayer(lg+1) {
		clz[0] = 0;
		for (int i = 1; i < (int)clz.size(); i++) {
			clz[i] = clz[i >> 1] + 1;
		}
		int tlg = lg;
		while (tlg > 1) {
			onLayer[tlg] = (int)layers.size();
			layers.push_back(tlg);
			tlg = (tlg+1) >> 1;
		}
		for (int i = lg-1; i >= 0; i--) {
			onLayer[i] = max(onLayer[i], onLayer[i+1]);
		}
		int betweenLayers = max(0, (int)layers.size() - 1);
		int bSzLog = (lg+1) >> 1;
		int bSz = 1 << bSzLog;
		indexSz = (n + bSz - 1) >> bSzLog;
		v.resize(n + indexSz);
		pref.assign(layers.size(), vector<SqrtTreeItem>(n + indexSz));
		suf.assign(layers.size(), vector<SqrtTreeItem>(n + indexSz));
		between.assign(betweenLayers, vector<SqrtTreeItem>((1 << lg) + bSz));
		build(0, 0, n, 0);
	}
};

Задачі

CodeChef - SEGPROD

Опис​

Побудова кореневого розбиття​

Будуємо дерево​

Оптимізація складності запиту​

Оновлення елементів​

Оновлення окремого елемента​

Наївний підхід​

Sqrt-дерево всередині sqrt-дерева​

Оновлення відрізка​

Перший підхід​

Другий підхід​

Реалізація​

Задачі​