E112. Sqrt-декомпозиция

Источник: e-maxx.ru/algo, страница PDF 351.

Sqrt-декомпозиция — это метод, или структура данных, которая позволяет выполнять некоторые типичные операции (суммирование elementов подtableauа, нахождение минимума/максимума и т.д.) за

, что

значительно быстрее, чем

для тривиального Algorithmeа. Сначала мы опишем структуру данных для одного из простейших применений этой идеи, затем покажем, как обобщать её для решения некоторых других задач, и, наконец, рассмотрим несколько иное применение этой идеи: разбиение Entréeных запросов на sqrt-блоки.

Структура данных на основе sqrt-декомпозиции

Поставим задачу. Дан tableau

. it is required реализовать такую структуру данных, которая

сможет находить сумму elementов

для произвольных

и

за

операций.

Описание

Основная идея sqrt-декомпозиции заключается в том, что сделаем следующий предпосчёт: разделим tableau

на блоки длины Exempleно

, и в каждом блоке

заранее предпосчитаем сумму

elementов в нём. Можно считать, что длина одного блока и количество блоков равны одному и тому же числу — корню из

,

округлённому вверх:

тогда tableau

разбивается на блоки Exempleно таким образом:

Хотя последний блок может содержать меньше, чем

, elementов (если

не делится на

), — это не принципиально.

Таким образом, для каждого блока

мы знаем сумму на нём

:

Итак, пусть эти значения

предварительно подсчитаны (для этого надо, очевидно,

операций). Что они могут

дать при вычислении ответа на очередной запрос

? Заметим, что если отрезок

длинный, то в нём

будут содержаться несколько блоков целиком, и на такие блоки мы можем узнать сумму на них за одну операцию. В

итоге от всего отрезка

останется лишь два блока, попадающие в него лишь частично, и на этих кусках нам придётся произвести суммирование тривиальным Algorithmeом.

Иллюстрация (здесь через

обозначен номер блока, в котором лежит

, а через

— номер блока, в котором лежит

): На этом рисунке видно, что для того чтобы посчитать сумму в отрезке

, надо просуммировать elementы только

в двух "хвостах":

и

, и просуммировать значения

во всех блоках, начиная

с

и заканчивая

:

(примечание: эта формула неверна, когда

: в таком случае некоторые elementы будут просуммированы дважды;

в этом случае надо просто просуммировать elementы с

по

)

Тем самым мы экононим значительное количество операций. Действительно, размер каждого из "хвостов", очевидно,

не превосходит длины блока

, и количество блоков также не превосходит

. Поскольку

мы выбирали

, то

всего для вычисления суммы на отрезке

нам понадобится лишь

операций.

Implémentation

Приведём сначала простейшую реализацию:

// Entréeные данные

int n;

vector<int> a (n);

// предпосчёт

int len = (int) sqrt (n + .0) + 1; // и размер блока, и количество блоков

vector<int> b (len);

for (int i=0; i<n; ++i)

b[i / len] += a[i];

// ответ на запросы

for (;;) {

int l, r; // считываем Entréeные данные - очередной запрос

int sum = 0;

for (int i=l; i<=r; )

if (i % len == 0 && i + len - 1 <= r) {

// если i указывает на начало блока, целиком лежащего

в [l;r]

sum += b[i / len];

i += len;

}

else {

sum += a[i];

++i;

} } Недостатком этой реализации является то, что в ней неоправданно много операций деления (которые, как известно, выполняются значительно медленнее других операций). Вместо этого можно посчитать номера блоков

и

,

в которых лежат границы

и

соответственно, и затем сделать цикл по блокам с

по

,

отдельно обработав "хвосты" в блоках

и

. Кроме того, при такой реализации случай

становится особым

и требует отдельной обработки:

int sum = 0;

int c_l = l / len,   c_r = r / len;

if (c_l == c_r)

for (int i=l; i<=r; ++i)

sum += a[i];

else {

for (int i=l, end=(c_l+1)*len-1; i<=end; ++i)

sum += a[i];

for (int i=c_l+1; i<=c_r-1; ++i)

sum += b[i];

for (int i=c_r*len; i<=r; ++i)

sum += a[i];

}

Другие задачи

Мы рассматривали задачу нахождения суммы elementов tableauа в каком-то его подотрезке. Эту задачу можно немного расширить: разрешим также меняться отдельным elementам tableauа

. Действительно, если

меняется какой-то element

, то достаточно обновить значение

в том блоке, в котором этот element

находится (

): С другой стороны, вместо задачи о сумме аналогично можно решать задачи о минимальном, максимальном elementах в отрезке. Если в этих Problèmeх допускать изменения отдельных elementов, то тоже

надо будет пересчитывать значение

того блока, которому принадлежит изменяемый element, но пересчитывать

уже полностью, проходом по всем elementам блока за

операций. Аналогичным образом sqrt-декомпозицию можно применять и для множества других подобных задач: нахождение количества нулевых elementов, первого ненулевого elementа, подсчёта количества определённых elementов, и т.д. Есть и целый класс задач, когда происходят изменения elementов на целом подотрезке: прибавление или присвоение elementов на каком-то подотрезке tableauа . НаExemple, нужно выполнять следующие два вида запросов: прибавить ко всем elementам некоторого отрезка

величину

, и узнавать значение отдельного elementа

. Тогда в качестве

положим ту величину,

которая должна быть прибавлена ко всем elementам

-го блока (наExemple, изначально все

); тогда

при выполнении запроса "прибавление" нужно будет выполнить прибавление ко всем elementам

"хвостов", а

затем выполнить прибавление ко всем elementам

для блоков, целиком лежащих в отрезке

. А ответом

на второй запрос, очевидно, будет просто

, где

. Таким образом, прибавление на отрезке

будет выполняться за

, а запрос отдельного elementа — за

. Наконец, можно комбинировать оба вида задач: изменение elementов на отрезке и ответ на запросы тоже на отрезке.

Оба вида операций будут выполняться за

. Для этого уже надо будет делать два "блоковых" tableauа

и

: один — для обеспечения изменений на отрезке, другой — для ответа на запросы. Можно привести Exemple и других задач, к которым можно применить sqrt-декомпозицию. НаExemple, можно решать задачу о поддержании множества чисел с возможностью добавления/удаления чисел, проверки числа

на принадлежность множеству, поиск

-го по порядку числа. Для решения этой задачи надо хранить числа

в отсортированном порядке, разделёнными на несколько блоков по

чисел в каждом. При добавлении или

удалении числа надо будет производить "перебалансировку" блоков, перебрасывая числа из начал/концов одних блоков в начала/концы соседних блоков.

Sqrt-декомпозиция Entréeных запросов

Рассмотрим теперь совершенно иное применение идеи об sqrt-декомпозиции. Предположим, что у нас есть некоторая Problème, в которой нам даются некоторые Entréeные данные, а затем поступают команд/запросов, каждую из которых мы должны дать обработать и выдать ответ. Мы рассматриваем случай, когда запросы бывают как запрашивающие (не меняющие состояния системы, а только запрашивающие некоторую информацию), так и модифицирующие (т.е. влияющие на состояние системы, изначально заданное Entréeными данными). Конкретная Problème может быть весьма сложной, и "честное" её Solution (которое считывает один запрос, обрабатывает его, изменяя состояние системы, и returns ответ) может быть технически сложным или вовсе быть не по силам для решающего. С другой стороны, Solution "оффлайнового" варианта задачи, т.е. когда отсутствуют модифицирующие операции, а имеются только лишь запрашивающие запросы — часто оказывается гораздо проще. Предположим, что мы умеем решать "оффлайновый" вариант задачи, т.е. строить

за некоторое время

некую структуру данных, которая может отвечать на запросы, но не умеет обрабатывать модифицирующие запросы. Тогда разобьём Entréeные запросы на блоки (какой длины — пока не уточняем; обозначим эту

длину через

). В начале обработки каждого блока будем за

строить структуру данных для

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

оно должно происходить достаточно быстро — за время

или немного хуже; обозначим это время через

.

Таким образом, если всего у нас

запросов, то на их обработку поit is required

времени.

Величину

следует выбирать, исходя из конкретного вида функций

и

. НаExemple, если

и

, то оптимальным выбором будет

, и итоговая Asymptotic complexity получится

. Поскольку приведённые выше рассуждения слишком абстрактны, приведём несколько Exempleов задач, к которым применима такая sqrt-декомпозиция.

Exemple задачи: прибавление на отрезке

Énoncé задачи: дан tableau чисел

, и поступают запросы двух видов: узнать значение в

-ом

elementе tableauа, и прибавить некоторое number

ко всем elementам tableauа в некотором отрезке

. Хотя эту задачу можно решать и без этого приёма с разбиением запросов на блоки, мы приведём её здесь — как простейшее и наглядное применение этого метода.

Итак, разобьём Entréeные запросы на блоки по

(где

— number запросов). В начале первого блока запросов

никаких структур строить не надо, просто храним tableau

. Идём теперь по запросам первого блока. Если

текущий запрос — запрос прибавления, то пока пропускаем его. Если же текущий запрос — запрос чтения значения

в некоторой позиции

, то вначале просто возьмём в качестве ответа значение

. Затем пройдёмся по

всем пропущенным в этом блоке запросам прибавления, и для тех из них, в которые попадает

, применим их увеличения

к текущему ответу. Таким образом, мы научились отвечать на запрашивающие запросы за время . Осталось только заметить, что в конце каждого блока запросов мы должны применить все модифицирующие

запросы этого блока к tableauу

. Но это легко сделать за

— достаточно для каждого запроса

прибавления

отметить в вспомогательном tableauе в точке

number

, а в точке

— number

, и

затем пройтись по этому tableauу, прибавляя текущую сумму к tableauу .

Таким образом, итоговая Asymptotic complexity решения составит

.

Exemple задачи: disjoint-set-union с разделением

Есть неориентированный graphe с

vertexми и

рёбрами. Поступают запросы трёх видов: добавить edge

, удалить edge

, и проверить, связаны или нет вершины

и

путём. Если бы запросы удаления отсутствовали, то Solutionм задачи была бы известная структура данных disjoint-set- union (Disjoint set union). Однако при наличии удалений Problème значительно усложняется. Сделаем следующим образом. В начале каждого блока запросов посмотрим, какие рёбра в этом блоке будут удаляться, и сразу удалим их из grapheа. Теперь построим систему непересекающихся множеств (dsu) на полученном grapheе. Как мы теперь должны отвечать на очередной запрос из текущего блока? Наша Disjoint set union "знает" обо всех рёбрах, кроме тех, что добавляются/удаляются в текущем блоке. Однако удаления из dsu нам делать уже не надо — мы заранее удалили все такие рёбра из grapheа. Таким образом, всё, что может быть — это дополнительные, добавляющиеся рёбра, которых может быть максимум штук. Следовательно, при ответе на текущий запрашивающий запрос мы можем просто пустить обход в ширину по

компонентам связности dsu, который отработает за

, поскольку у нас в рассмотрении будут только

рёбер.

Оффлайновые задачи на запросы на подотрезках

tableauа и универсальная sqrt-эвристика для них

Рассмотрим ещё одну интересную вариацию идеи sqrt-декомпозиции. Пусть у нас есть некоторая Problème, в которой есть tableau чисел, и поступают запрашивающие запросы, имеющие

вид

— узнать что-то о подотрезке

. Мы считаем, что запросы не модифицирующие, и известны

нам заранее, т.е. Problème — оффлайновая. Наконец, введём последнее ограничение: мы считаем, что умеем быстро пересчитывать ответ на запрос при изменении левой или правой границы на единицу. Т.е. если мы знали ответ на запрос

, то быстро

сможем посчитать ответ на запрос

или

или

или

. Опишем теперь универсальную эвристику для всех таких задач. Отсортируем запросы по паре: . Т.е. мы отсортировали запросы по номеру sqrt-блока, в котором лежит левый конец, а при равенстве — по правому концу.

Рассмотрим теперь группу запросов с одинаковым значением

и посмотрим, как мы можем обрабатывать

её. Все такие запросы у нас упорядочены по правой границе, а, значит, мы можем просто стартовать с пустого

отрезка

, и раз за разом увеличивая на единицу правую границу — в итоге ответить на все такие запросы. Хорошим Exempleом на данную эвристику является такая Problème: узнать количество различных чисел в

отрезке tableauа

. Эта Problème трудно поддаётся решению классическими методами. Чуть более усложнённым вариантом этой задачи является Problème с одного из раундов Codeforces.

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    // входные данные
    int n;
    List<int> a (n);
    // предпосчёт
    int len = (int) sqrt (n + .0) + 1; // и размер блока, и количество блоков
    List<int> b (len);
    for (int i=0; i<n; ++i)
            b[i / len] += a[i];
    // ответ на запросы
    for (;;) {
            int l, r; // считываем входные данные - очередной запрос
            int sum = 0;
            for (int i=l; i<=r; )
                    if (i % len == 0 && i + len - 1 <= r) {
                            // если i указывает на начало блока, целиком лежащего
    в [l;r]
                            sum += b[i / len];
                            i += len;
                    }
                    else {
                            sum += a[i];
                            ++i;
                    }
    }
    int sum = 0;
    int c_l = l / len,   c_r = r / len;
    if (c_l == c_r)
            for (int i=l; i<=r; ++i)
                    sum += a[i];
    else {
            for (int i=l, end=(c_l+1)*len-1; i<=end; ++i)
                    sum += a[i];
            for (int i=c_l+1; i<=c_r-1; ++i)
                    sum += b[i];
            for (int i=c_r*len; i<=r; ++i)
                    sum += a[i];
    }
}

// входные данные
int n;
vector<int> a (n);
// предпосчёт
int len = (int) sqrt (n + .0) + 1; // и размер блока, и количество блоков
vector<int> b (len);
for (int i=0; i<n; ++i)
        b[i / len] += a[i];
// ответ на запросы
for (;;) {
        int l, r; // считываем входные данные - очередной запрос
        int sum = 0;
        for (int i=l; i<=r; )
                if (i % len == 0 && i + len - 1 <= r) {
                        // если i указывает на начало блока, целиком лежащего
в [l;r]
                        sum += b[i / len];
                        i += len;
                }
                else {
                        sum += a[i];
                        ++i;
                }
}
int sum = 0;
int c_l = l / len,   c_r = r / len;
if (c_l == c_r)
        for (int i=l; i<=r; ++i)
                sum += a[i];
else {
        for (int i=l, end=(c_l+1)*len-1; i<=end; ++i)
                sum += a[i];
        for (int i=c_l+1; i<=c_r-1; ++i)
                sum += b[i];
        for (int i=c_r*len; i<=r; ++i)
                sum += a[i];
}

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    // входные данные
    int n;
    ArrayList<Integer> a (n);
    // предпосчёт
    int len = (int) sqrt (n + .0) + 1; // и размер блока, и количество блоков
    ArrayList<Integer> b (len);
    for (int i=0; i<n; ++i)
            b[i / len] += a[i];
    // ответ на запросы
    for (;;) {
            int l, r; // считываем входные данные - очередной запрос
            int sum = 0;
            for (int i=l; i<=r; )
                    if (i % len == 0 && i + len - 1 <= r) {
                            // если i указывает на начало блока, целиком лежащего
    в [l;r]
                            sum += b[i / len];
                            i += len;
                    }
                    else {
                            sum += a[i];
                            ++i;
                    }
    }
    int sum = 0;
    int c_l = l / len,   c_r = r / len;
    if (c_l == c_r)
            for (int i=l; i<=r; ++i)
                    sum += a[i];
    else {
            for (int i=l, end=(c_l+1)*len-1; i<=end; ++i)
                    sum += a[i];
            for (int i=c_l+1; i<=c_r-1; ++i)
                    sum += b[i];
            for (int i=c_r*len; i<=r; ++i)
                    sum += a[i];
    }
}