8000 Update src/data_structures/fenwick.md · cp-algorithms/cp-algorithms@195a1cd · GitHub
[go: up one dir, main page]

Skip to content < 8000 script type="application/json" data-target="react-partial.embeddedData">{"props":{"docsUrl":"https://docs.github.com/get-started/accessibility/keyboard-shortcuts"}}

Commit 195a1cd

Browse files
JJCUBERadamant-pwn
andauthored
Update src/data_structures/fenwick.md
Co-authored-by: Oleksandr Kulkov <adamant.pwn@gmail.com>
1 parent 7da7a2b commit 195a1cd

File tree

< 8000 span class="prc-TooltipV2-Tooltip-cYMVY" data-direction="se" aria-hidden="true" id=":R2atdab:">Expand file tree

1 file changed

+0
-1
lines changed

1 file changed

+0
-1
lines changed

src/data_structures/fenwick.md

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,6 @@ The Fenwick tree is a data structure which:
1919

2020
The most common application of a Fenwick tree is _calculating the sum of a range_.
2121
For example, using addition over the set of integers as the group operation, i.e. $f(x,y) = x + y$: the binary operation, $*$, is $+$ in this case, so $A_l * A_{l+1} * \dots * A_r = A_l + A_{l+1} + \dots + A_{r}$.
22-
(In terms of $f$, this would be $f(A_l, f(A_{l+1}, f(f(\dots, \dots),A_r)))$, or any other equivalent way to write this using associativity.)
2322

2423
The Fenwick tree is also called a **Binary Indexed Tree** (BIT).
2524
It was first described in a paper titled "A new data structure for cumulative frequency tables" (Peter M. Fenwick, 1994).

0 commit comments

Comments
 (0)
0