Здравствуйте, камрады 🦖
По запросам из комментариев сегодня у нас на разборе корневая декомпозиция. Разберем на примере известной задачки:
Дан массив. Нужно ответить на q запросов одного из двух типов:
1. Найти сумму на отрезке [l, r]
2. Увеличить все элементы на отрезке [l, r] на x

Сделаем вид что про Дерево Отрезков (кстати, мы его разбирали ранее!) мы не знаем

Идея
1. Делим задачу на блоки размером примерно sqrt(n)
2. Подсчитываем что-то в каждом блоке
3. Запросы обрабатываем частично через блоки, частично поштучно

Инициализация

const int maxn = 1e5, c = 330; // c ≈ √n
int a[maxn];       // исходный массив
int b[c];          // суммы по блокам
int add[c];        // отложенные прибавления для блоков

// Предподсчет сумм по блокам
for (int i = 0; i < n; i++)
    b[i / c] += a[i];

1. Сумма

int sum(int l, int r) {
    int res = 0;
    while (l <= r) {
        // Если начинаем с начала блока и он целиком в запросе
        if (l % c == 0 && l + c - 1 <= r) {
            res += b[l / c];          // берем сумму всего блока
            l += c;                   // перепрыгиваем блок
        } else {
            res += a[l] + add[l / c]; // учитываем отложенное прибавление
            l++;
        }
    }
    return res;
}

2. Обновление

void upd(int l, int r, int x) {
    while (l <= r) {
        if (l % c == 0 && l + c - 1 <= r) {
            b[l / c] += c * x;
            add[l / c] += x;
            l += c;
        }
        else {
            b[l / c] += x;
            a[l] += x;
            l++;
        }
    }
 }

Обе операции работают за O(sqrt(n))

Когда юзаем?
- Когда нужна простота реализации
- Когда дерево отрезков избыточно
- Для задач, где операции неассоциативны

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


@postupashki_prog