Алгоритм Мо
Теперь обсудим еще одно решение задачи прибавления и суммы на отрезке. Допустим, что все запросы даны нам заранее и запросов обновления нет. Для каждого запроса закинем его в блок, где лежит его левая граница:
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