You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: src/data_structures/fenwick.md
+14-14Lines changed: 14 additions & 14 deletions
Original file line number
Diff line number
Diff line change
@@ -15,17 +15,17 @@ Fenwick tree is a data structure which:
15
15
16
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
-
Fenwick tree was first described in the paper titled "A new data structure for cumulative frequency tables" (Peter M. Fenwick, 1994).
18
+
Fenwick tree was first described in a paper titled "A new data structure for cumulative frequency tables" (Peter M. Fenwick, 1994).
19
19
20
20
### Description
21
21
22
-
For the sake of simplicity, we will assume that function $f$ is just *sum function*.
22
+
For the sake of simplicity, we will assume that function $f$ is just a *sum function*.
23
23
24
24
Given an array of integers $A[0 \dots N-1]$. Fenwick tree is an array $T[0 \dots N-1]$, where each of its elements is equal to the sum of elements of $A$ in some range $[g(i); i]$:
25
25
26
26
$$T_i = \sum_{j = g(i)}^{i}{A_j}$$
27
27
28
-
where $g$ is some function that satisfies $(g(i) \le i)$, and we will define it a bit later.
28
+
where $g$ is some function that satisfies $(g(i) \le i)$ and we will define it a bit later.
29
29
30
30
> **Note:** Fenwick tree presented here **does support** 0-based indexing (in case you were told that it does not support it).
31
31
@@ -46,29 +46,29 @@ def inc (int i, int delta):
46
46
47
47
The function `sum` works as follows:
48
48
49
-
1. firstly, it adds the sum of the range$[g(r); r]$ (i.e. $T[r]$) to the `result` ;
50
-
2. then, it "jumps" to the range$[g(g(r)-1); g(r)-1]$, and adds this range's sum to the `result` ;
51
-
3. and so on, till it "jumps"from$[0; g(g( \dots g(r)-1 \dots -1)-1)]$ to $[g(-1); -1]$; that is where the `sum` stops jumping.
49
+
1. first, it adds the sum of the range$[g(r); r]$ (i.e. $T[r]$) to the `result`
50
+
2. then, it "jumps" to the range$[g(g(r)-1); g(r)-1]$, and adds this range's sum to the `result`
51
+
3. and so on, until it "jumps"from$[0; g(g( \dots g(r)-1 \dots -1)-1)]$ to $[g(-1); -1]$; that is where the `sum` function stops jumping.
52
52
53
53
The function `inc` works with the same analogy, but "jumps"in the direction of increasing indices:
54
54
55
55
1. sums of the ranges $[g(j); j]$ that satisfy the condition $g(j) \le i \le j$ are increased by `delta` , that is `t[j] += delta` .
56
56
57
-
It is obvious that complexity of both `sum`and`upd` do depend on the function $g$. We will define the function $g$in such a way, so that, both of the operations will have logarithmic complexity $O(lg N)$.
57
+
It is obvious that complexity of both `sum`and`upd` do depend on the function $g$. We will define the function $g$in such a waythat both of the operations have a logarithmic complexity $O(lg N)$.
58
58
59
-
**Definition of $g(i)$.** Let us consider the least significant digit of $i$in binary. If this digit is$0$, then let $g(i) = i$. Otherwise, if we examine digits of $i$inbinary (in decreasing order of significance), then $i$should end withone or more$1$'s. We convert these $1$'s to $0$'s and assign the new number as the value of $g(i)$.
59
+
**Definition of $g(i)$.** Let us consider the least significant digit of $i$in binary. If this digit is$0$, then let $g(i) = i$. Otherwise, the binary representation of $i$will end withat least one$1$ bit. We will flip allthese tailing $1$'s (so they become $0$'s)anddefine the result asa value of $g(i)$.
60
60
61
61
There exists a trivial solution for the non-trivial operation described above:
62
62
63
63
```
64
64
g(i) = i & (i+1)
65
65
```
66
66
67
-
where `&`is logical AND operator. It isnot hard to convince yourself that this solution does the same thing as the operation described above.
67
+
where `&`isa logical AND operator. It isnot hard to convince yourself that this solution does the same thing as the operation described above.
68
68
69
-
Now, we need to find a way to find allsuch $j$'s, so that, *g(j) <= i <= j*.
69
+
Now, we need to find a way to find all$j$'s, such that *g(j) <= i <= j*.
70
70
71
-
It is easy to see that we can find all such $j$'s, by starting with $i$ and replacing the least significant one of all $0$'s with a $1$. For example, for$i=10$ we have:
71
+
It is easy to see that we can find all such $j$'s by starting with $i$ and flipping the least significant zero bit. For example, for $i = 10$ we have:
72
72
73
73
```
74
74
j=10, binary 0001010
@@ -79,13 +79,13 @@ j = 63, binary 0111111
79
79
...
80
80
```
81
81
82
-
Not surprisingly, there also exists a simple way to do the above operation:
82
+
Unsurprisingly, there also exists a simple way to do the above operation:
83
83
84
84
```
85
85
h(j) = j | (j+1)
86
86
```
87
87
88
-
where `|`isthe logical OR operator.
88
+
where `|`isa logical OR operator.
89
89
90
90
### Implementation: finding sum in one-dimensional array
91
91
@@ -121,7 +121,7 @@ struct FenwickTree {
121
121
122
122
### Implementation: finding minimum of $[0; r]$ in one-dimensional array
123
123
124
-
It is obvious that there is no way of finding minimum of range$[l; r]$ using Fenwick tree, as Fenwick tree can only answer the queries of type [0; r]. Additionally, each time a value is`update`'d, new value should be smaller than the current value (because, the $min$ function is not reversible). These, of course, are significant limitations.
124
+
It is obvious that there is no way of finding minimum of range$[l; r]$ using Fenwick tree, as Fenwick tree can only answer queries of type [0; r]. Additionally, each time a value is`update`'d, new value should be smaller than the current value (because, the $min$ function is not reversible). These, of course, are significant limitations.
0 commit comments