148
правок
Изменения
→Описание
== Описание ==
''Привидем описание для операции суммированияминимума''
Дан массив <tex>A[0 \ldots n-1]</tex>. Cделаем следующий предпосчёт: разделим массив A на блоки длины <tex>\sqrt{n}</tex> (округлённому к целому), и в каждом блоке заранее предпосчитаем нужную операцию в нём. Пусть len — это длина блока <tex>(len \approx \sqrt{n})</tex>, а <tex>cnt = \left\lceil \frac{n}{len} \right\rceil</tex> — количество блоков:
Через <tex>b_k</tex> мы обозначили результат предпосчёта в k-ом подотрезке.
Для того чтобы посчитать сумму в минимум на отрезке <tex>[l \ldots r]</tex>, надо просуммировать элементы только в двух найти минимум среди элементов "хвостаххвостов": <tex>[l \ldots (k+1)len-1]</tex> и <tex>[(p+1)len \ldots r]</tex>, и просуммировать значения минимума среди <tex>b_i</tex> во всех блоках, начиная с k и заканчивая p:<tex>\sum_min_{i = l}^r a_i = \sum_min(\min_{i = l}^{(k + 1)len - 1} + (a_i ),\sum_min_{i = k}^p ( b_i + ),\sum_min_{i = p + 1}^r (a_i))</tex>
Теперь разрешим изменять элементы. Если меняется какой-то элемент <tex>a_i</tex>, то достаточно обновить пересчитать значение <tex>b_k</tex> в том блоке, в котором этот элемент находится:
<tex>b_k\ += a_i \min(new_value, a_j)</tex>, где <tex>a_j</tex> - old\_a_i\_valэлементы блока b_k</tex>
<tex>(k = i / len)</tex>
