4
4
5
5
Let, $f$ be some _ reversible_ function and $A$ be an array of integers of length $N$.
6
6
7
- Fenwick tree is a data structure, which:
7
+ Fenwick tree is a data structure which:
8
8
9
9
* 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;
10
10
* updates the value of an element of $A$ in $O(lg\ n)$ time;
@@ -13,7 +13,7 @@ Fenwick tree is a data structure, which:
13
13
14
14
> Fenwick tree is also called Binary Indexed Tree.
15
15
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$).
17
17
18
18
Fenwick tree was first described in the paper titled "A new data structure for cumulative frequency tables" (Peter M. Fenwick, 1994).
19
19
@@ -174,16 +174,16 @@ struct FenwickTree2D {
174
174
};
175
175
```
176
176
177
- # # Problems in Online Judge
177
+ # # Practice Problems
178
178
179
179
* [UVA 12086 - Potentiometers](https:// uva.onlinejudge.org/ index.php? option = com_onlinejudge& Itemid = 8 & category = 24 & page = show_problem& problem = 3238 )
180
180
* [LOJ 1112 - Curious Robin Hood](http:// www.lightoj.com/ volume_showproblem.php? problem = 1112 )
181
181
* [LOJ 1266 - Points in Rectangle](http:// www.lightoj.com/ volume_showproblem.php? problem = 1266 " 2D Fenwick Tree" )
182
182
183
183
# ## Other sources
184
184
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 / )
187
187
188
188
189
189
Translated by [sylap97](http:// codeforces.com/ profile/ sylap97)
0 commit comments