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 does not equal the original array]

【Conclusion】

Prefix sum array $S$: $S_i = \sum_{k=0}^{i}{a_i}$, easily derived $a_i = S_i - S_{i-1}$ [Difference]
Difference array $X$: $X_i=a_i-a_{i-1}$, easily derived $a_i=\sum_{k=0}^{i}X_i$ [Prefix Sum]

【Observation】

The prefix sum array and the difference array do not add information; they are just another representation of the same information.
Knowing one array allows us to derive the others:
- Given array $a$: —Prefix Sum—>$S$ array, —Difference—>$X$ array
- Given $S$ array: —Difference—>$a$ array
- Given $X$ array: —Prefix Sum—>$a$ array
[PS] The prefix sum operation and the difference operation are actually two inverse operations.
❗ However, different representations correspond to different time complexities for different operations, as seen below.

【Problem Introduction】

① Original array range sum operation

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

② Original array range modification operation

Before modification:
- On array $a$: $a_0,a_1,a_2,a_3,a_4,a_5,a_6$
- On array $X$: $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: [Range addition]
- On array $a$: $a_0,a_1,a_2[+d],a_3[+d],a_4[+d],a_5[+d],a_6$
- On array $X$: $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 array $X$: $O(1)$

【Conclusion】

Prefix sum array: Optimizes range sum operations.
Difference array: Optimizes range element modification operations.

【Thought】❗

The efficiency of single-point modification in the prefix sum array is $O(n)$, because it requires modifying the changed point and all subsequent prefix sum elements.
The value of elements in the prefix sum array is related to all items in the original array! So, how can we weaken this relationship?

👉Fenwick Tree: Weakens the above relationship, sacrificing a bit of query efficiency [trade-off].

lowbit function#

【Key in Fenwick Tree】

$lowbit(i)$: Represents the weight of the last 1 in the binary representation of the number $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: [Two's complement of a negative number] = [One's complement of a positive number] + 1
- For example: $-3 = ~3 + 1 = ~0011 + 1 = 1101$
- ❗ Two's complement representation turns subtraction into addition [there is no subtraction in computers].

Fenwick Tree#

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

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$, i.e., the number of elements that make up the prefix sum.

Single Point Modification#

To modify the value at position $i$, we need to continuously modify $f(i)=i + lowbit(i)$: $C[i],\ C[f(i)],\ C[f(f(i))],\ ...,\ until\ index\gt n$.
For example:
- Modify $a[1]$: $C[1],C[2],C[4],C[8]$ <whereas 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 forward, each time check the previous bit of $i$ —> $i - lowbit(i)$, until $i=0$.
- Single-point modification: Modify backward, each time check 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 basic prefix sum array: query worsens, single-point modification improves, overall time complexity improves.
Prerequisite for use: Must be convertible to a prefix sum problem.

In-Class Exercises#

HZOJ-329: Weakened Integer Problem#

Sample Input

Sample Output

Thought Process
- Involves range modification and single-point query operations.
  - Range modification 👉 Single-point operation of the difference array ① [Optimal, see above].
  - Single-point query 👉 Prefix sum of the difference array ②.
- Since we need to maintain both prefix sum ② and perform single-point modification ①, we can:
  - ⭐ Use Fenwick Tree to maintain the difference array of the original array.
  - Of course, we can also use Segment Tree.
Code
- ❗ Place the range modification operation on the difference array, converting it to [single-point modification]; convert the single-point query operation to the prefix sum of the difference array.
- Learning the code for the Fenwick Tree, its implementation generally does not change [very versatile].
  - ⭐ Single-point modification, prefix sum query.
- Store the difference array, using a pre variable to record the previous element.
- [PS] The indices of the difference array and the prefix sum array generally start from 1, as their 0th position is 0.

HZOJ-330: Strengthened Integer Problem#

Sample Input

Sample Output

Thought Process
- Involves range modification and range query operations.
  - Range modification 👉 Single-point modification of the difference array ① [same as the previous problem: OJ-329].
  - But how to perform range queries? 👉 Two prefix sums ②, see below.
- Range Query problem transformation:
  - ① Since the difference array is introduced, we need to revolve around the difference array to transform the range sum problem.
  - ② The range sum $Query(l,r)=S(r)-S(l-1)$, so focus on analyzing the transformation of $S$ to $X$ [difference array].
  - ③ Derive the following equation:
    - $\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 line of the equation is evident.
    - The derivation of the second line can be seen below:
      - For $\sum_{k=1}^{i}\sum_{y=1}^{k}{X_y}\ (Ⅰ)$, assume $i=4$, list the values of $k$.
      - By observation, we find that $(Ⅰ)=\sum_{k=1}^{i}[(i-k+1)\times X_k]$.
      - Grouping the variables allows us to proceed.
  - ④ 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, ensuring time efficiency during range modifications.
Code
- Focus on the overall thought process, clarifying the numbering $0\to 2$.
- Main methods:
  - add, query methods: Basic operations of the Fenwick Tree, single-point modification && prefix sum query.
  - modify method: Simultaneously maintain two Fenwick Trees.
  - S method: Obtain the prefix sum of the original sequence through the prefix sums of two difference arrays [focus on the formulas derived in the thought process].
- [Thought] The two maintained Fenwick Trees are both related to the difference array, so during range modifications, the time complexity for maintaining the Fenwick Tree remains at the $O(log\ n)$ level [2 × 2 single-point modifications].
  - ❗ If thinking about range queries, using the original array is more convenient, thus maintaining the Fenwick Trees for both the original array and the difference array. However, during range modifications, maintaining the Fenwick Tree for the original array has a time complexity of $O(n \times log\ n)$, which is worse than just using the original array, corresponding to $O(n)$.
- [PS] If using char to receive operation information, consider the existence of previous newline characters when using scanf.
  - However, cin will not have this issue; using character arrays will also avoid this problem.

Additional Knowledge Points#

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

Tips#

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