Sqrt-декомпозиция (корневая оптимизация)

Sqrt-декомпозиция — это метод, или структура данных, позволяющая в режиме онлайн проводить такие операции, как подсчет суммы на отрезке за image и обновление элемента за image. Существуют более эффективные структуры, такие как дерево фенвика или дерево отрезков, которые оба запроса обрабатывают за image. Однако я хочу рассказать про корневую оптимизацию, т.к. в этом методе заложена идея, применимая к задачам другого типа.


Постановка задачи

Пусть нам задан массив A[i], на который поступают запросы вида:
  • посчитать сумму на отрезке [L; R] (позже, мы поймем, что аналогично можно вычислять функции min, max, gcd и др.
  • добавить к элементу A[i], delta
Наивная реализация

Мы можем предрасчитать массив частичных сумм, а именно:
 for(int j = 0; j < i; j++) B[j] += A[i];
и тогда на запрос суммы [L; R], мы будем возвращать B[R]-B[L-1] за image. Однако на запрос изменения, потребует пересчета частичных сумм (содержащих этот элемент) и в худшем случае составит асимптотику порядка image, что не есть хорошо.

Построение декомпозиции

Основной идеей будет то, что image * image = image. А именно, если у нас есть image элементов, то всех их мы можем разбить на image блоков, где каждый длиной image, кроме, может быть, последнего. Затем для всех блоков мы посчитаем сумму чисел на нем, сразу можно увидеть, что вспомогательный массив будет занимать image памяти.
Опишем построение массива sqrtSums[]:

int len = (int)sqrt(n) + 1; //длина каждого "sqrt-отрезка"
int sqrtSums[MAXN], st = 0; //массив предпросчитанных сумм
for(int i = 0; i < n; i++)
	sqrtSums[i / len] += A[i];


Описание запросов

Запрос суммы (RSQ)

Рассмотрим запрос суммы [L; R], для «быстрого» ответа на него, необходимо максимально использовать уже имеющуюся информацию. Как мы уже говорили, Sum[L; R] = Sum[0, R] — Sum[0; L-1]. Осталось научиться обрабатывать запрос Sum[0; R]. Заметим, что несколько первых отрезков ([0; len-1], [len; 2*len-1], ...) будут полностью входить в запрос [0; R], а значит мы можем использовать информацию из sqrtSums[] (за image, так как отрезков всего image). Однако у нас останется «хвостик» вида: [k*len; k*len + delta] (delta < len, т.к. иначе, мы сможем включить еще один отрезок [k*len; (k+1)*len-1]), его мы сможем посчитать вручную (delta < len, на асимптотику, image, не повлияет). Приведем пример реализации:

int getPartSum(int r)
{
	int it = 0, res = 0;
	while((it+1) * len -1 <= r)
		res += sqrtSums[it++]; //прибавляем предпосчитанные отрезки, пока можем
	for(int i = it*len; i <=r; i++)
		res += A[i]; //прибавляем "хвост"
	return res;
}
int getSum(int l, int r)
{
	if(l == 0)
		return getPartSum(r); 
	else
		return getPartSum(r) - getPartSum(l-1); 
}

Запрос на изменение элемента


Во многих структурах, для реализации данного запроса, требуется опуститься по дереву, или посчитать хеш-функцию, или еще что-то… Однако тут нам необходимо поменять всего 2 значения (каждый элемент входит в ровно один «sqrt-отрезок»)

int incElement(int index, int delta)
{
	A[index] += delta;
	sqrtSums[index/len] += delta;
}


Range Min/Max/Gcd Query


Чтобы отвечать на запросы RMQ(Range Min / Max Query) нужно почти тоже самое, что и для сумм. Однако стоит отметить, чтобы обновить элемент «в тупую», нам потребуется image времени (при обновлении элемента, пересчитывать min/max на всем «sqrt-отрезке»), но если наложить на обновления некоторые ограничения, то мы добьемся оценки image. А именно, при решении задачи поиска минимума/максимума, разрешать только уменьшать/увеличивать элемент.
Код для обновления минимума:

int decElement(int index, unsigned int delta) //delta - на сколько уменьшить элемент
{
	A[index] -= delta;
	sqrtSums[index/len] = min(sqrtSums[index/len], A[index]);
}

Аналогично для обновления максимума:

int incElement(int index, unsigned int delta) //delta - на сколько увеличить элемент
{
	A[index] += delta;
	sqrtSums[index/len] = max(sqrtSums[index/len], A[index]);
}

Нужно добавить, что в задаче RMQ, задача не сводится к [0; R] — [0; L-1], т.е. придется вычислять минимум/максимум с L по R (не считая заново, полностью входящие в [L; R] «sqrt-отрезки», подумайте, почему асимптотика не поменяется, а чистое время работы может даже улучшится...).

Для вычисления GCD (Greatest Common Divisor), мы не сможем использовать ту «фишку», что мы провернули для min/max. Поэтому обе операции вычисляются за image.
Код для GCD (для минимума и максимума функции getGCD заменятся на min/max):

int getGCD(int a, int b)
{
	while(a && b)
	{
		if(a < b)
			b %= a;
		else
			a %= b;
	}
	return a + b;
}
int gcdRQ(int l, int r)
{
	int cur_gcd = A[l++];
	for(int i = l; i <= r;)
		if (i % len == 0 && i + len - 1 <= r) {
			cur_gcd = getGCD(cur_gcd, b[i / len]);
			i += len; //перескок через "sqrt-отрезок"
		}
		else 
			cur_gcd = getGCD(cur_gcd, A[i++]);
}


Источники


Пользовался этим сайтом, а именно.
Так как вдохновила на статью лекция из Харьковской Зимней Компьютерной Школы, то кину сайт, возможно скоро там появится сборник за этот год, с видео-лекциями.

Пока все, надеюсь, что было понятно.
Share post
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 10

    +1
    Да, я тоже очень вдохновилась после этой лекции. Ощутила, что я на самом деле вообще нифига не шарю в структурах и деревьях (хотя до этого была другого мнения) (=

    А других источников кроме e-maxx'а нет? А про КД-дерево и иже с ними? (=
      0
      В Кормене очень подробно описываются хеши и деревья (особенно красно-черные). А по поводу КД-дерева, думаю в сборнике будет хорошо все описано =) А, да, вот сборники с видео-лекциями за прошлые года (есть почти все =) )
        0
        Ну Кормена уже до дыр зачитали. И все эти красно-черные деревья — баян (= А вот квадро-деревья и т.п. — это новенькое (=
        А вообще, как выяснилось, на английской Вики деревьев на любой вкус сколько хочешь! (=
      0
      В начале поста упомянута некая «идея, применимая к задачам другого типа». А, собственно, что за идея?
        0
        Хотел расписать одну задачу с которой недавно столкнулся, но статья затянулась…
          0
          Если я не ошибаюсь, такая статья уже была. Именно особенность с предварительным подсчётом сумм и квадратный корень мне запомнились.

          Тем не менее, хорошо написано и +1.
            0
            Возможно Вашь алгоритм можно улучшить, в случае если L>=R. В случае если это условие выплняется, то sqrt суммы для R частично считать не нужно, они уже посчитаны для L.
            Кроме того, если бы в статье были приведены примеры Unit тестов то материал был бы более усваиваем.
              0
              Алгоритм, как минимум, можно улучшить (в среднем) за счет того что, мы будем просто считать сумму не как разность частичных сумм, а «подъемами» снизу (как в дереве отрезков).
                0
                Да, я не учел, что можно считать кумулятивную сумму.
                Вот моя реализация на Java на github.
              0
              Та же идея применима к спискам с пропусками, если ограничить высоту списка двойкой. В этом случае легко показать, что оптимальным является расстановка узлов высоты два как раз через n1/2 узлов нижнего уровня. Это гарантирует время поиска в списке порядка O(n1/2). Более точно это время оценивается, как 2n1/2. Идею можно развить, если ввести не два уровня, а например, три. Тогда оптимальным будет расположение «высоких» узлов через n1/3 узлов каждого уровня. Этот даст нам время поиска порядка 3n1/3. Если довести эти рассуждения до логического конца, то при k=log2n уровнях (в этом случае получаются минимально возможные подмассивы длины два) получим время поиска равное 2log2n — это кмк оптимальный результат полноценного списка с пропусками. И подозреваю, что такое же время будет у нормального дерева отрезков…

              Only users with full accounts can post comments. Log in, please.