Алгоритм Мо

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

s_dec[l / s].a.push_back({l, r});

Затем внутри каждого блока отсортируем запросы по правой границе. Теперь давайте пройдемся по каждому блоку, поддерживая текущий отрезок, на который мы знаем ответ. И если текущий отрезок равен отрезку из запроса запоминать его, как ответ.

struct q {
    int l, r, index;
};

struct block {
    vector<q> a;
};

for(int i = 0; i < q; i++) {
    s_dec[l / s].a.push_back({l, r, i});
}

for(int i = 0; i < s; i++) {
    sort(all(s_dec[i].a), comp);
}

for(int i = 0; i < s; i++) {
    int l = i * s, r = i * s;
    int ans = 0;
    for(int j = 0; j < s_dec[i].a.size(); j++) {
        int tl = s_dec[i].a[j].l, tr = s_dec[i].a[j].r;
        while (r > tr){
            r—;
            ans -= a[r];
        }
        while(r < tr) {
            ans += a[r];
            r++;
        }
        while(l > tl) {
            l--;
            ans += a[l];
        }
        while(l < tl) {
            ans -= a[l];
            l++;
        }
        answ[s_dec[i].a[j].index] = ans;
}

Подумаем над асимптотикой данного алгоритма, для каждого запроса левая граница пройдет не более, чем длину блока, но при этом правая граница идет только вперед, а следовательно для одного блока пройдет не более, чем длину массива, то есть суммарно алгоритм работает за $O(N\sqrt(M) + M\sqrt(N))$.

Алгоритм Мо может помочь нам в ответе на гораздо более сложные вопросы - k-ая статистика на отрезке, медиана отрезка, наиболее встречающийся элемент на отрезке и так далее.

---

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin