Episode 0 - Fenwick Trees

The first broadcast of Algorithms Live! This week will be lecture style. I'll present a popular data structure in competitive programming, the Fenwick Tree. The data structure is also known as a binary indexed tree or BIT.

01:25 - Overview, when a BIT is useful
02:50 - Range sums
07:02 - Idea of Fenwick tree; construction by hand
10:55 - Computing prefix sum
14:55 - Updating element
17:12 - Walking the BIT, lowest one bit
20:33 - Implementing BIT in java
24:16 - Counting inversions problem
30:28 - Kth largest element problem
44:52 - Range updates and point queries
50:25 - Recommended problems
52:00 - Next week announcement, chat

Thank you to Mikhail Goncharov for the time links!

For extra practice you can try the following problems:
http://usaco.org/index.php?page=viewproblem2&cpid=91
https://open.kattis.com/problems/moviecollection

Topcoder also has an excellent tutorial on this data structure:
https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/

Видео Episode 0 - Fenwick Trees канала Algorithms Live!