5 Fenwick Tree

Course Content#

Prefix Sum Array and Difference Array#

[Assumption] Original array $a$: $a_i,\ i\in[0,\ n]$ (note that $a_0=0$) [otherwise, the prefix sum of the difference array will not equal the original array]

[Derivation]

Prefix sum array $S$: $S_i = \sum_{k=0}^{i}{a_i}$, and we have $a_i = S_i - S_{i-1}$ [difference]
Difference array $X$: $X_i=a_i-a_{i-1}$, and we have $a_i=\sum_{k=0}^{i}X_i$ [prefix sum]

[Observation]

Prefix sum array and difference array do not add any new information, they are just alternative representations of the same information
Given one array, we can derive the other arrays
- Given array $a$: ——prefix sum——> $S$ array, ——difference——> $X$ array
- Given $S$ array: ——difference——> $a$ array
- Given $X$ array: ——prefix sum——> $a$ array
[PS] Prefix sum operation and difference operation are actually two inverse operations
❗ However, different representations correspond to different time complexities for different operations, as shown below

[Problem Introduction]

① Original array interval sum operation

Operation on array $a$: $O(n)$
Operation on $S$ array: $O(1)$, we can obtain the interval sum of array $a$ in the range $[j,\ i]$ as $S_i-S_{j-1}$

② Original array interval modification operation

Before modification:
- On array $a$: $a_0,a_1,a_2,a_3,a_4,a_5,a_6$
- On $X$ array: $X_1=a_1-a_0,X_2=a_2-a_1,X_3=a_3-a_2,X_4=a_4-a_3,X_5=a_5-a_4,X_6=a_6-a_5$
After modification: [interval addition]
- On array $a$: $a_0,a_1,a_2[+d],a_3[+d],a_4[+d],a_5[+d],a_6$
- On $X$ array: $X_1=a_1-a_0,X_2=a_2-a_1[+d],X_3=a_3-a_2,X_4=a_4-a_3,X_5=a_5-a_4,X_6=a_6-a_5[-d]$
It can be seen that
- Operation on array $a$: $O(n)$
- Operation on $X$ array: $O(1)$

[Conclusion]

Prefix sum array: optimized for interval sum operation
Difference array: optimized for interval element modification operation

[Consideration] ❗

The efficiency of single-point modification on the prefix sum array is $O(n)$ because it requires modifying all prefix sum elements after the changing point
The value of each prefix sum array element is related to all previous items in the original array! So, how can we weaken this relationship?

👉 Fenwick Tree: Weaken the above relationship at the cost of slightly reduced query efficiency [trade-off]

lowbit Function#

[Key in Fenwick Tree]

$lowbit(i)$: Represents the weight of the last 1 in the binary representation of $i$
Calculation formula: $lowbit(i) = i\ &\ (-i) = i\ &\ (\sim i + 1)$
Example: $lowbit(10010000)$
- Obtained the position of the rightmost 1, very clever
Negative numbers are represented in two's complement notation: Complement of [negative number] = Complement of [positive number] + 1
- For example: $-3 = ~3 + 1 = ~0011 + 1 = 1101$
- ❗ Two's complement notation turns subtraction into addition [no subtraction in computers]

Fenwick Tree#

⭐ Fenwick Tree is essentially an optimization of the prefix sum array, mainly reflected in the single-point modification operation

Intuitive Comparison: Prefix Sum Array#

In the Fenwick Tree, $C[i]$ represents the sum of the first $lowbit(i)$ items starting from $a[i]$
The Fenwick Tree is more flattened
Both have the same space consumption

Prefix Sum Query#

Prefix sum: $S[i]=S[i-lowbit(i)]+C[i]$
For example
- $S[7]=S[7-1]+C[7]=S[6-2]+C[6]+C[7]=C[4]+C[6]+C[7]$
- $S[12]=S[12-4]+C[12]=C[8]+C[12]$
Time complexity: $O(log\ n)$
[PS] The number of 1s in $(i)_2$ is the number of elements in the prefix sum

Single-Point Modification#

To modify the value at position $i$, we need to continuously modify the bits $f(i)=i + lowbit(i)$: $C[i]$, $C[f(i)]$, $C[f(f(i))]$, ..., until the index is greater than $n$
For example
- Modify $a[1]$: $C[1],C[2],C[4],C[8]$ <For a normal prefix sum array, the first 8 items need to be modified>
Time complexity: $O(log\ n)$

Summary#

$lowbit()$ function: crucial
Two operations
- Prefix sum query: count backward, each time check the previous bit of $i$ ——> $i - lowbit(i)$, until $i=0$
- Single-point modification: modify forward, each time modify the next bit of $i$ ——> $i + lowbit(i)$, until $i>n$
Time efficiency
- Prefix sum query: $O(log\ n)$, single-point modification: $O(log\ n)$
- Compared to the most common prefix sum array: query becomes worse, single-point modification becomes better, overall time complexity becomes better
Prerequisite for use: it must be convertible to a prefix sum problem

In-Class Exercises#

HZOJ-329: Weakened Integer Problem#

Sample Input

Sample Output

Idea
- Involves interval modification and single-point query operations
  - Interval modification 👉 Single-point modification of the difference array ① [Optimal, see above]
  - Single-point query 👉 Prefix sum of the difference array ②
- We need to maintain both the prefix sum ② and perform single-point modification ①, so
  - ⭐ We can use the Fenwick Tree to maintain the difference array of the original array
  - Of course, we can also use Segment Tree
Code
- ❗ Perform interval modification on the difference array, which is converted to single-point modification; perform single-point query, which is converted to prefix sum of the difference array
- The code for the Fenwick Tree implementation generally does not change [very versatile]
  - ⭐ Single-point modification, prefix sum query
- Store the difference array and use a pre variable to record the previous element
- [PS] The indices of the difference array and the prefix sum array generally start from 1, because their 0th position is always 0

HZOJ-330: Strengthened Integer Problem#

Sample Input

Sample Output

Idea
- Involves interval modification and interval query operations
  - Interval modification 👉 Single-point modification of the difference array ① [Same as the previous problem: HZOJ-329]
  - But how to perform interval query? 👉 Two prefix sums ②, see below
- Interval query problem conversion
  - ① Since the difference array is introduced, we need to convert the interval sum problem around the difference array
  - ② Interval sum $Query(l,r)=S(r)-S(l-1)$, so the focus is on the conversion from $S$ to $X$ [difference array]
  - ③ The derivation is as follows
    - $\begin{aligned}&S_i=\sum_{k=1}^ia_k=\sum_{k=1}^{i}\sum_{y=1}^{k}{X_y}\&=\sum_{k=1}^i[(i+1)X_k-k\times X_k]=(i+1)\sum_{k=1}^iX_k-\sum_{k=1}^i(k\times X_k)\end{aligned}$
    - The first equation is obvious
    - The second equation is derived as follows
      - For $\sum_{k=1}^{i}\sum_{y=1}^{k}{X_y}\ (Ⅰ)$, assuming $i=4$, list the values of $k$
      - By observation, $(Ⅰ)=\sum_{k=1}^{i}[(i-k+1)\times X_k]$
      - Place the variables in groups, and it can be obtained
  - ④ Let $Y_k=k\times X_k$, then $S_i=(i+1)\sum_{k=1}^iX_k-\sum_{k=1}^iY_k$
  - [Conclusion] $S_i$ can be obtained through 2 prefix sum arrays related to the difference array, thus completing the $Query(l,r)$ problem
    - Two Fenwick Trees need to be maintained
- [PS] The two Fenwick Trees maintained are both related to the difference array, so the time complexity of maintaining the Fenwick Trees during interval modification is still $O(log\ n)$ [2 × 2 single-point modifications]
  - ❗ If you want to perform interval queries and use the original array, it is more convenient to maintain the Fenwick Trees of the original array and the difference array. However, when performing interval modifications, the time complexity of maintaining the Fenwick Trees of the original array is $O(n \times log\ n)$, which is worse than using only the original array, which corresponds to $O(n)$ complexity
- [PS] If you use char to receive the operation information, you need to consider the existence of the previous newline character when using scanf
  - However, cin does not have this problem; there is no such problem when using character arrays

Additional Knowledge#

Fenwick Tree VS. Segment Tree
- The code for the Fenwick Tree is shorter
- In terms of space —— $n: 4n$ [the size of the original array is $n$]

Tips#

You can think of the prefix product version of the Fenwick Tree
- Addition and multiplication are essentially the same, they are both multiplicative functions
- [PS] Change the initial 0 to 1, and all += operations to *= operations
What is the principle of the Fenwick Tree? —— Zhihu
- Understand the relationship with $lowbit(i)$