Skip to content

Commit 52f8db2

Browse files
authored
Unescape *'s
It seems that they render differently through github markdown vs the one used for the official site.
1 parent eba7fac commit 52f8db2

1 file changed

Lines changed: 3 additions & 3 deletions

File tree

src/data_structures/fenwick.md

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -7,18 +7,18 @@ e_maxx_link: fenwick_tree
77
# Fenwick Tree
88

99
Let $f$ be some group operation (a binary associative function over a set with an identity element and inverse elements) and $A$ be an array of integers of length $N$.
10-
Denote $f$'s infix notation as $\*$; that is, $f(x,y) = x\*y$ for arbitrary integers $x,y$.
10+
Denote $f$'s infix notation as $*$; that is, $f(x,y) = x*y$ for arbitrary integers $x,y$.
1111
(Since this is associative, we will omit parentheses for order of application of $f$ when using infix notation.)
1212

1313
The Fenwick tree is a data structure which:
1414

15-
* calculates the value of function $f$ in the given range $[l, r]$ $\left(\text{i.e. }A_l \* A_{l+1} \* \dots \* A_r)\right)$ in $O(\log N)$ time
15+
* calculates the value of function $f$ in the given range $[l, r]$ $\left(\text{i.e. }A_l * A_{l+1} * \dots * A_r)\right)$ in $O(\log N)$ time
1616
* updates the value of an element of $A$ in $O(\log N)$ time
1717
* requires $O(N)$ memory (the same amount required for $A$)
1818
* is easy to use and code, especially in the case of multidimensional arrays
1919

2020
The most common application of a Fenwick tree is _calculating the sum of a range_.
21-
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}$.
21+
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}$.
2222
(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.)
2323

2424
The Fenwick tree is also called a **Binary Indexed Tree** (BIT).

0 commit comments

Comments
 (0)