Fenwick Tree (Binary Index Tree) - Quick Tutorial and Source Code Explanation
In this tutorial we’ll discuss a computer science data structure called "Fenwick Tree", also known as "Binary Index Tree". This data structure is used to efficiently perform range queries, such as addition, multiplication and XOR. We’ll develop a simple visual explanation of how it works. Then, we’ll dive into the details of how to actually implement it by walking over source code of sum() and update() functions, which run in O(log n) time complexity. Finally, we'll discuss the source code of an algorithm that efficiently populates Binary Index Trees with data in O(n) running time.
Full source code implementation of Fenwick Tree in Java:
https://bitbucket.org/StableSort/play/src/master/src/com/stablesort/fenwick/FenwickTree.java
The paper by Peter Fenwick: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.8917&rep=rep1&type=pdf
Wikipedia: https://en.wikipedia.org/wiki/Fenwick_tree
Written and narrated by Andre Violentyev
Видео Fenwick Tree (Binary Index Tree) - Quick Tutorial and Source Code Explanation канала Stable Sort
Full source code implementation of Fenwick Tree in Java:
https://bitbucket.org/StableSort/play/src/master/src/com/stablesort/fenwick/FenwickTree.java
The paper by Peter Fenwick: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.8917&rep=rep1&type=pdf
Wikipedia: https://en.wikipedia.org/wiki/Fenwick_tree
Written and narrated by Andre Violentyev
Видео Fenwick Tree (Binary Index Tree) - Quick Tutorial and Source Code Explanation канала Stable Sort
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
Segment Tree Data Structure - Min Max Queries - Java source code花花酱 Fenwick Tree / Binary Indexed Tree - 刷题找工作 SP3Longest Increasing Subsequence O(n log n) dynamic programming Java source codeFenwick Tree range queriesPrim's AlgorithmRolling Hash Function Tutorial, used by Rabin-Karp String Searching AlgorithmFenwick Tree or Binary Indexed TreeGodel's 1st Incompleteness Theorem - Proof by DiagonalizationSegment Trees - The Best Introduction in 10 minsCreating a Phylogenetic TreeUnderstand Calculus in 10 MinutesHow to send a self-correcting message (Hamming codes)자료구조: 바이너리 인덱스 트리(Binary Indexed Tree, BIT, 펜윅 트리) 10분 정복Partition Problem - 2 subsets of equal sum, as closely as possible - tutorial and source codeTutorial: Binary Indexed Tree (Fenwick Tree)KD-Tree Nearest Neighbor Data StructureAlgorithms: Bit ManipulationQuadtrees and Octrees for Representing Spatial InformationLazy Propagation Segment TreeEpisode 0 - Fenwick Trees