This unit covers the Fenwick Tree datastructure, otherwise known as Binary Indexed Tree. We apply the Fenwick Tree to the problem of Dynamic Range Sum Query and see the pros and cons of using a Fenwick Tree over a Segment Tree.
Complementary notes can be found in section 2.4.3 of the book Competitive Programming 3.
- Unit 1: Complexity
- Unit 2: Linear data structures
- Unit 8: Segment Tree
- UVa 12086 - Potentiometers
- UVa 12532 - Interval Product
- NWERC 2011 Problem C - Movie Collection
- Codeforces 504 Problem B - Misha and Permutations Summation
- Topcoder - Binary Indexed Trees
- Peter M. Fenwick - A New Data Structure for Cumulative Frequency Tables