TreesEvidence Contributing
Binary Indexed Tree (Fenwick Tree)
Use a BIT/Fenwick tree to answer prefix sum queries or range queries with point updates in O(log n) time, typically when the operation is associative and invertible.
Practice Problems: 3
Difficulty: 0 Easy·1 Medium·2 Hard
Core technique
Review the technique, then try the mapped problems below. The right approach depends on each problem's constraints.
- Core Strategy: Use a BIT/Fenwick tree to answer prefix sum queries or range queries with point updates in O(log n) time, typically when the operation is associative and invertible.