Skip to content

Commit 9213005

Browse files
authored
Clean up Fenwick Tree article
1 parent a32a2f8 commit 9213005

File tree

1 file changed

+5
-5
lines changed

1 file changed

+5
-5
lines changed

src/data_structures/fenwick.md

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,7 @@
44

55
Let, $f$ be some _reversible_ function and $A$ be an array of integers of length $N$.
66

7-
Fenwick tree is a data structure, which:
7+
Fenwick tree is a data structure which:
88

99
* calculates the value of function $f$ in the given range $[l; r]$ (i.e. $f(A_l, A_{l+1}, \dots, A_r)$) in $O(lg\ n)$ time;
1010
* updates the value of an element of $A$ in $O(lg\ n)$ time;
@@ -13,7 +13,7 @@ Fenwick tree is a data structure, which:
1313

1414
> Fenwick tree is also called Binary Indexed Tree.
1515
16-
The most common application of Fenwick tree is used for _calculating the sum of a range_ (i.e. $f(A_1, A_2, \dots, A_k) = A_1 + A_2 + \dots + A_k$).
16+
The most common application of Fenwick tree is _calculating the sum of a range_ (i.e. $f(A_1, A_2, \dots, A_k) = A_1 + A_2 + \dots + A_k$).
1717

1818
Fenwick tree was first described in the paper titled "A new data structure for cumulative frequency tables" (Peter M. Fenwick, 1994).
1919

@@ -174,16 +174,16 @@ struct FenwickTree2D {
174174
};
175175
```
176176

177-
## Problems in Online Judge
177+
## Practice Problems
178178

179179
* [UVA 12086 - Potentiometers](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3238)
180180
* [LOJ 1112 - Curious Robin Hood](http://www.lightoj.com/volume_showproblem.php?problem=1112)
181181
* [LOJ 1266 - Points in Rectangle](http://www.lightoj.com/volume_showproblem.php?problem=1266 "2D Fenwick Tree")
182182

183183
### Other sources
184184

185-
Wikipedia: [en.wikipedia.org/wiki/Fenwick_tree](http://en.wikipedia.org/wiki/Fenwick_tree)
186-
Topcoder: [community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees](http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees)
185+
* [Fenwick tree on Wikipedia](http://en.wikipedia.org/wiki/Fenwick_tree)
186+
* [Binary indexed trees tutorial on TopCoder](https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/)
187187

188188

189189
Translated by [sylap97](http://codeforces.com/profile/sylap97)

0 commit comments

Comments
 (0)