Дарахти Фенвик
Дарахти Фенвик — ин сохтори додаҳоест, ки функсияҳои зеринро дастгирӣ мекунад:
Ғояи асосӣ то андозае ба дарахти қитъаҳо монанд аст. Маҳз қитъа сохта мешаванд, ки дар онҳо мо суммаи элементҳои он қитъаро нигоҳ медорем. Ба тавре ки:
Баъдан массиви сохта мешавад.
Дар суммаи элементҳои -ро нигоҳ медорем.
Ва савол ба миён меояд: кадом маҳз қитъаҳоро бояд сохт? Яъне кадом қиматҳои -ро гирифтан лозим?
— ин ададест, ки бо инверт кардани охирин бити дар намоиши дуӣ-и ба даст меояд.
Масалан:
Метавон пай бурд, ки:
Ин ҳама мавқеъҳои мебошанд, ки барои онҳо иҷро мешавад:
Ва ҳамаи чунин мавқеъҳоро метавон чунин гирифт:
Чаро ин кор мекунад — метавон ҳамчун машқ барои хонанда гузошт.
while (i <= n) {
...
i += (i & -i);
}
struct fenwick {
vector<long long> t;
fenwick(int n) : t(n, 0) {}
void upd(int x, long long y) {
while (x < (int)t.size()) {
t[x] += y;
x += x & -x;
}
}
long long get(int x) {
long long res = 0;
while (x > 0) {
res += t[x];
x -= x & -x;
}
return res;
}
};