БО @bminaiev_blog
Forwarded from Боря дорешивает
This post (sticker, poll or similar) has no web preview. Open in Telegram
a[pos] += xa[i] для i <= r.a будем поддерживать некоторый массив f. Сами функции выглядят так:void add(int pos, int x) {
for (int i = pos; i < n; i = up(i)) {
f[i] += x;
}
}
int sum(int pos) {
int res = 0;
for (int i = pos; i >= 0; i = down(i)) {
res += f[i];
}
return res;
}up и down это какие-то магические битовые операции. Этот пост предназначен для людей, которые раньше знали этот код наизусть, а теперь не смогут вспомнить как именно пишутся up и down. Расскажу больше деталей про дерево Фенвика, может вы научитесь выводить формулы для up и down самостоятельно.up можно использовать разные функции, но будем использовать "проставить младший нулевой бит". Довольно легко понять, что ее можно написать как up(i) = i | (i + 1). А теперь давайте поймем как подобрать правильную функцию down для этой up.f заключается в том, что в ячейке pos хранится сумма некоторого подотрезка элементов из a. Причем правый конец этого отрезка это pos. Например, в pos = 010110111 хранится сумма элементов, которые подходят под маску 010110??? (таких всего 8 штук). Т.е. нужно посмотреть на отрезок из единиц, стоящих в самый младших разрядах, и заменить их на любые биты.sum(010110111)? Нужно взять f[010110111] (соответствует сумме a[010110000..010110111]), а потом добавить к ней sum(010101111). По сути переход от 010110111 к 010101111 это и есть применение функции down.down можно описать словами следующим образом:down(i) = (i & (i + 1)) - 1.find(s), которая за логарифм находит наибольшую позицию r такую, что сумма чисел a[0..r] <= s (если все a неотрицательные).