6 Fenwick Tree and Segment Tree Exercises

For knowledge about segment trees, please refer to: 《Interview and Written Test Algorithms Part 2》——4 Segment Trees

For knowledge about Fenwick trees, please refer to: 《Interview and Written Test Algorithms Part 2》——5 Fenwick Trees

HZOJ-331: Lost Cows#

Lost_cows

Sample Input

Sample Output

Thought Process
- 【Question 1】Is the answer unique? ❓√
  - Observe from the end and work backwards
  - The value of the last animal is based on all the previous animals, meaning all information is known
  - Therefore, if its value is $x$, meaning there are $x$ animals before it that are smaller, its index will be $x+1$
  - Further: For the second last animal $y$, its index can be found by looking for the $y+1$ ranked index among the indices of all animals excluding the last one
- 【Question 2】How to know which indices are left? ❓Marking Array
  - Use a marking array to record whether each index [subscript] is available, with 1 for available and 0 for unavailable
    - At this point, the indices marked as 1 in the marking array are the available indices
- The general process is shown in the figure below, in the order of ①→④
  - Need to count the index corresponding to the $k$-th 1 in the current marking array
  - For example, in steps ③ and ④, the current cow has a larger index than the 1 cow before it, so its index is the second largest among the remaining available indices, which is 3, and then mark it
- 【Problem Transformation】Prefix Sum of the Marking Array
  - The index corresponding to the $k$-th 1 can actually be obtained through the prefix sum
  - The prefix sum at the $x$ [index] position in the marking array represents the number of available indices before the $x$ position [including itself], which is $k$ [input + 1]
  - Therefore, in the prefix sum array, find the first occurrence of the 【$k$】 value to get the corresponding 【$x$】 index
    - Note the first occurrence: the $x$ position in the marking array must be 1 [subsequent 0s will not increase the prefix sum]
- 【Conclusion】⭐
  - Observing from the end, determine the index of each cow in turn
    - Find the 【input + 1】-th index among the remaining available indices
  - Maintain the prefix sum of the marking array, which is monotonic
    - Therefore, binary search can be performed on the prefix sum array to find the first occurrence of the value and obtain the corresponding index
  - Involves maintaining the prefix sum of the marking array and point updates, so Fenwick Tree can be used
- 【Key Technique】Marking array, using the prefix sum of the marking array
- 【PS】Time Complexity: $O(n\ log\ n)$
Code
- Fenwick Tree: Maintain the marking array using prefix sums
- Looking for the first occurrence of 【input + 1】, corresponding to which position
  - Note the first occurrence! There may be multiple indices corresponding to 【input + 1】 due to the presence of 0
- Remember to mark it after finding, 1->0
- [PS] Input starts from the second position

HZOJ-332: Buying Tickets#

Sample Input

Sample Output

77 33 69 51

Thought Process
- Similar to the previous question [HZOJ-331]
  - The first column of the input 👉 represents how many people are in front of a person
- Similarly, work backwards, using the Fenwick tree to maintain the prefix sum of the marking array, find the index of the first occurrence of the 【input + 1】 value, and then match the index [actual position] with $val$
Code
- Key: Work backwards 👉 Special Binary Search 👉 Marking [Maintain Fenwick Tree] 👉 Store Answer Array

HZOJ-328: Loulan Totem#

Sample Input

5
1 5 3 2 4

Sample Output

3 4

Thought Process
- 【Note】The input is a permutation from $1\to n$
- 【Key】For a certain point, the number of "^" formed by it is $a \times b$
  - Where $a$ is the number of points before it that are smaller, and $b$ is the number of points after it that are smaller
- 【Question】How to quickly find the number of elements $a$ that are less than the point $X$ before it?
  - Use a marking array to record which elements have appeared before the current position, marking as 1 if they have appeared, otherwise marking as 0
  - Following the order from 0️⃣→3️⃣: When reaching the value $X=4$, values 1, 2, 3, and 5 have already been marked, so the number of elements before $X$ that are smaller is $a=3$, which gives $b=X - 1 - a = 0$, marking value 4
- 【Formalization】Let the current element value be $X$, and its position be $i$, then
  - ① The number of elements less than $X$ before it is $a$
  - ② The number of elements less than $X$ after it is $(X - 1) - a$
  - ③ The number of elements greater than $X$ before it is $(i - 1) - a$
  - ④ The number of elements greater than $X$ after it is $(n - X) - ((i - 1) - a)$
  - ⭐ Actually
    - $a$ equals the prefix sum of the marking array at position $X$; the last three quantities can all be derived from $a$
    - ① × ② gives the number of "^", and ③ × ④ gives the number of "V"
- 【Data Structure】Point updates and prefix sum queries of the marking array can use a Fenwick Tree
- 【PS】The idea is similar to HZOJ-516: Cow Inscriptions — Refer to Solution
  - HZOJ-516 can directly calculate the quantity through equality
  - This problem requires judging the size relationship, so a Fenwick tree based on the marking array is used
Code
- Marking array: Mark elements that have appeared as 1
- Focus on the conversion formula, which can be understood through diagrams
- [PS] Change line 64 from $val[i]$ to $val[i] + 1$, and move it before line 58, which also works [to deepen understanding]

HZOJ-333: Maximum Subarray Sum in Range#

Sample Input

Sample Output

2
-1

Thought Process
- 【Key】Maintain the maximum continuous subarray sum in range; use Segment Tree
- 【Consideration】The maximum subarray sum of the parent node's range can come from three possible sources, take the maximum
  - ① Left sub interval $max$, ② Left sub interval $rmax$ + right sub interval $lmax$, ③ Right sub interval $max$
- 【Therefore】The values to maintain [for each node]
  - Maximum subarray sum $max$, left side maximum subarray sum $lmax$, right side maximum subarray sum $rmax$, interval sum $sum$
  - Why maintain the interval sum $sum$? ❓
    - Consider the maintenance of $lmax$ and $rmax$
    - The $lmax$ of the parent node's range can come from two possible sources, take the maximum
      - Ⅰ) Left sub interval $lmax$, Ⅱ) Left sub interval $lmax$ + right sub interval $lmax$ [with conditions]
      - ❗ The condition for the second source to hold is that the left sub interval's $lmax$ spans the entire sub interval
      - Rather than checking this condition, it is better to directly maintain the interval sum $sum$ [$\le lmax$]
- 【Note】When seeking the final answer, it is done in order from left to right, merging two at a time
  - For example: When querying the interval $|①②③④⑤|$
  - Traverse the nodes in the order of $①②③④⑤$
  - The merging order is $①+②$, $①②+③$, $①②③+④$, $①②③④+⑤$, merging two nodes into one each time
  - Finally, when $①②③④⑤$ is merged into one node, output the corresponding $max$ of that node
  - See the code for specifics
- [PS] Segment tree problems can be a bit challenging
Code
- ⭐Key Points: Operations numbered $0\to 2$
  - 0, Use of sum: Reduce conditional checks
  - 1, Upward update strategy: Pass in 3 parameters for convenience, also for the merging strategy on line 88
  - 2, Query merging strategy: Each time merge one node, temporarily store the merged node in another variable, then return
- [PS]
  - There are no lazy updates in this segment tree as it does not involve interval modifications
  - According to the problem statement, special handling is required for the case $x>y$

Tips#

Fenwick trees are generally used to solve prefix sum problems
Segment trees have broader applications, generally used to solve interval operation problems that include prefix sums
Based on the nature of the problem, find suitable algorithms and data structures