Skip to content

Data Structures -> Fenwick Tree

Low-level prefix structure for point updates, range sums, compressed coordinates, and order statistics.

  • Topic slug: data-structures/fenwick-tree
  • Tutorial page: Open tutorial
  • Ladder page: Open ladder
  • Repo problems currently tagged here: 4
  • Repo companion pages: 0
  • Curated external problems: 6

Microtopics

  • lowbit
  • point-add
  • prefix-sum
  • range-sum
  • coordinate-compression
  • kth-order-statistic

Learning Sources

Source Type
AtCoder ACL Fenwick Primary
cp-algorithms Fenwick Reference
OI Wiki Fenwick Reference

Practice Sources

Source Type
AtCoder Library Practice Contest Practice
CSES Problem Set Practice

Curated External Problems

Core

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Dynamic Range Sum Queries CSES Medium - Data-Structure-Heavy; Query-Heavy Prefix Sums; Point Updates; Binary Indexed Tree Point-Update; Range-Sum A standard first Fenwick-tree task with point updates and range sums.
Range Update Queries CSES Medium - Data-Structure-Heavy Difference Arrays; Prefix Sums; Fenwick Tree Basics Difference Array; Range-Update; Range-Add A good bridge between difference arrays and Fenwick-style prefix maintenance.

Classics

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Point Add Range Sum Library Checker Medium - Query-Heavy; Data-Structure-Heavy Fenwick Tree; Point Updates; Prefix Sums Range-Sum A concise official benchmark for the core Fenwick use case.
Salary Queries CSES Medium - Query-Heavy; Data-Structure-Heavy Fenwick Tree; Coordinate Compression; Frequency Counting Coordinate-Compression; Range-Count; Compression; Rank-Query A canonical frequency-query problem where Fenwick trees shine after compression.

Advanced

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Forest Queries II CSES Hard - Data-Structure-Heavy; Cross-Topic Fenwick Tree; 2D Grids; Rectangle Sums 2D-Fenwick; Rectangle-Query; Grid-Updates; Grid; Point-Update A strong advanced benchmark for extending Fenwick ideas into two dimensions.
Range Add Range Sum Library Checker Hard - Query-Heavy; Data-Structure-Heavy Fenwick Tree Tricks; Difference Arrays; Range Sums Range-Update A strong benchmark for the classic two-Fenwick range-add/range-sum pattern.

Repo Problems

Code Title Fit Difficulty Pattern Note Solution
CVP00001 Ô ăn quan primary hard circular updates; range-add point-query; query-from-initial-state Note Code
DISTINCTVALUESQUERIES Distinct Values Queries secondary hard offline right-endpoint sweep; last occurrence activation; fenwick range count Note Code
RANGEUPDATEQUERIES Range Update Queries secondary medium difference array updates; fenwick on diff; range add point query Note Code
SUBTREEQUERIES Subtree Queries secondary medium euler tour flattening; subtree interval; fenwick point set range sum Note Code

Regeneration

python3 scripts/generate_problem_catalog.py