Fenvik daraxti
Fenwick daraxti quyidagi funksiyalarni qo‘llab-quvvatlaydigan ma’lumotlar tuzilmasidir:
Asosiy g‘oya segment daraxtiga biroz o‘xshaydi. Aynan ta segment yaratiladi, ularda biz o‘sha segment elementlari yig‘indisini saqlaymiz. Shunday qilib:
Keyin massivi yaratiladi.
da biz elementlar yig‘indisini saqlaymiz.
Va savol tug‘iladi: aynan qaysi segmentlarni qurish kerak? Ya’ni, ning qaysi qiymatlarini olish kerak?
— ning ikkilik ko‘rinishidagi oxirgi bitini teskari qilish orqali olinadigan son.
Masalan:
Shuni payqash mumkin:
Bular quyidagi shart bajariladigan barcha pozitsiyalardir:
Va bunday barcha pozitsiyalarni quyidagicha olish mumkin:
Nega bu ishlashi o‘quvchi uchun mashq sifatida qoldirilishi mumkin.
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;
}
};