Pull to refresh

Дерево Фенвика

Algorithms *
Sandbox
Здравствуй, Хабрахабр. Сейчас я хочу рассказать о такой структуре данных как дерево Фенвика. Впервые описанной Питером Фенвиком в 1994 году. Данная структура похожа на дерево отрезков, но проще в реализации.

Что это?


Дерево Фенвика — это структура данных, дерево на массиве, которая обладает следующими свойствами:
• позволяет вычислять значение некоторой обратимой операции F на любом отрезке [L; R] за логарифмическое время;
• позволяет изменять значение любого элемента за O(log N);
• требует памяти O(N);
Читать дальше →
Total votes 81: ↑73 and ↓8 +65
Views 46K
Comments 38

Дерево Фенвика для максимума

Programming *
Про дерево Фенвика многие знают. Многие его используют. Однако считается, что деревом Фенвика нельзя находить максимум/минимум.
Мол, эта операция не имеет обратной. Однако небольшие изменения алгоритма позволяют нам решить и эту задачу тоже.
NB: Статья написана для тех, кто знает, что такое дерево Фенвика и описывает его модификацию для максимума.Тем, кто не знает, что такое дерево Фенвика, рекомендуется прочитать об этом где-нибудь, хоть в Кормене, хоть в статье на хабре.
Читать дальше →
Total votes 14: ↑10 and ↓4 +6
Views 14K
Comments 9

Дерево Фенвика с модификацией на отрезке

Programming *Algorithms *
С этой структурой данных можно ознакомиться в этом посте и её модификацией для нахождения максимума в этом. Но я нигде не встречал реализацию с изменением элементов на отрезке, поэтому решил поделиться тем, что сумел получить самостоятельно.
Читать дальше →
Total votes 27: ↑26 and ↓1 +25
Views 18K
Comments 6