148
правок
Изменения
→Описание
Для того чтобы посчитать сумму в отрезке <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_{i = l}^r a_i = \sum_{i = l}^{(k + 1)len - 1} + a_i \sum_{i = k}^p b_i + \sum_{i = p + 1}^r a_i</tex>
Теперь разрешим изменять элементы. Если меняется какой-то элемент <tex>a_i</tex>, то достаточно обновить значение <tex>b_k</tex> в том блоке, в котором этот элемент находится:
<tex>b_k\ += a_i - old\_a_i\_val</tex>
<tex>(k = i / len)</tex>
==Оценка сложности==
