6 Practice of Fenwick Tree and Segment Tree

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

For knowledge about binary indexed trees, please refer to: 《Interview and Written Test Algorithms》——5 Binary Indexed Tree

HZOJ-331: Lost Cows#

Lost_cows

Sample Input

Sample Output

Idea
- Is the answer unique? Yes
  - Observe from the end
  - The value of the last animal depends on all the previous animals, so we have all the information
  - If the value of the last animal is $x$, which means there are $x$ animals smaller than it, then its index is $x+1$
  - Further, for the second last animal $y$, it needs to find the index of the $y+1$th smallest number in the remaining indices except the last one, which is its own index
- How to know which indices are left? Use a marking array
  - Use a marking array to record whether each index is available or not, 1 for available and 0 for not available
    - The indices marked as 1 in the marking array are the available indices
- The process is shown in the following figure, following the order of ①→④
  - We need to count the $k$th 1 in the current marking array
  - For example, in steps ③ and ④, the current cow is larger than 1 cow in front of it, so its index is the second largest index in the remaining available indices, which is 3, then mark it as not available
- The problem is transformed into finding the $k$th 1 in the marking array, which can be obtained through the prefix sum of the marking array
  - The prefix sum of the $x$[index] position in the marking array represents the number of available indices before the $x$[index], including itself, which is $k$[input+1]
  - So, in the prefix sum array, find the first occurrence of the value $k$ to get the corresponding index $x$
    - Note that it should be the first occurrence: the $x$th position in the marking array must be 1 [the following 0 will not increase the prefix sum]
- Conclusion ⭐
  - Observe from the end and determine the index of each cow one by one
    - Find the $k$th index in the remaining available indices
  - Maintain the prefix sum of the marking array, which is monotonically increasing
    - So, we can use binary search on the prefix sum array to find the first occurrence of the value and get the corresponding index
  - It involves maintaining the prefix sum of the marking array and updating a single point, so we can use a binary indexed tree
- Key Technique: Marking array and prefix sum of the marking array
- PS: Time complexity: $O(n\ log\ n)$
Code
- Binary indexed tree: Maintain the marking array using the prefix sum
- Find the first occurrence of the [input+1]th index in the prefix sum array
- Remember to mark it as not available, 1->0
- [PS] The input starts from the second position

HZOJ-332: Buying Tickets#

Sample Input

Sample Output

77 33 69 51

Idea
- Similar to the previous problem [HZOJ-331]
  - The first column of the input represents the number of people in front of a certain person
- Similarly, we count backwards and use a binary indexed tree to maintain the marking array and find the first occurrence of the [input+1]th index, and then associate the index with the value
Code
- Key: Count backwards, special binary search, and mark as not available [maintain binary indexed tree] to store the answer array

HZOJ-328: Loulan Totem#

Sample Input

5
1 5 3 2 4

Sample Output

3 4

Idea
- 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$
  - $a$ is the number of elements smaller than it in front of it, $b$ is the number of elements smaller than it behind it
- Problem: How to quickly calculate the number $a$ of elements smaller than a certain point $X$ in front of it?
  - Use a marking array to record which elements have appeared before the current position, mark them as 1, otherwise mark them as 0
  - When reaching the value $X=4$, the elements 1, 2, 3, and 5 have been marked, so the number of elements smaller than $X=4$ in front of it is $a=3$, then calculate $b=X - 1 - a = 0$, and mark the value 4
- Formulas: Let $X$ be the current element value and $i$ be the element position, then
  - ① The number of elements smaller than $X$ in front of it is $a$
  - ② The number of elements smaller than $X$ behind it is $(X - 1) - a$
  - ③ The number of elements larger than $X$ in front of it is $(i - 1) - a$
  - ④ The number of elements larger than $X$ behind it is $(n - X) - ((i - 1) - a)$
  - ⭐ In fact
    - $a$ is the prefix sum of the marking array; the other three numbers can be calculated based on $a$
    - ① × ② gives the number of "^", ③ × ④ gives the number of "V"
- Data Structure: Binary indexed tree can be used for single point modification and prefix sum query of the marking array
- PS: Similar to HZOJ-516: Cow Inscriptions - Refer to Solution
  - HZOJ-516 can directly calculate the number by checking equality
  - In this problem, we need to compare the values, so we use a binary indexed tree based on the marking array
Code
- Key: Count backwards, maintain the marking array using a binary indexed tree, and store the answer array
- [PS] Change line 64 $val[i]$ to $val[i] + 1$, and move it before line 58, it will still work [deepen the understanding]

HZOJ-333: Maximum Subarray Sum in an Interval#

Sample Input

Sample Output

2
-1

Idea
- Key: Maintain the maximum sum of contiguous subarrays in an interval; use a segment tree
- Idea: For a parent node, there are 3 possible sources for the maximum subarray sum in its interval, choose the maximum one
  - ① Maximum sum of the left sub interval, ② Maximum sum of the left sub interval plus the maximum sum of the right sub interval, ③ Maximum sum of the right sub interval
- What to maintain [for each node]
  - Maximum subarray sum $max$, maximum subarray sum on the left side $lmax$, maximum subarray sum on the right side $rmax$, and the sum of the interval $sum$
  - Why do we need to maintain the sum of the interval $sum$?
    - Think about maintaining $lmax$ and $rmax$
    - There are 2 possible sources for the $lmax$ of the parent node's interval, choose the maximum one
      - Ⅰ) $lmax$ of the left sub interval, Ⅱ) $lmax$ of the left sub interval plus $lmax$ of the right sub interval [with a condition]
      - ❗ The condition for the second source to be valid is that the $lmax$ of the left sub interval spans the entire sub interval
      - Instead of checking this condition, it is easier to maintain the sum of the interval $sum$ [$\le lmax$]
- Note: When calculating the final answer, we merge nodes in order from left to right, two at a time
  - For example, when querying the interval $|①②③④⑤|$
  - Traverse the nodes in the order of $①②③④⑤$
  - The merge order is $①+②$, $①②+③$, $①②③+④$, $①②③④+⑤$, merging two nodes into one each time
  - After merging $①②③④⑤$ into one node, output the $max$ of that node
  - See the code for details
- PS: This is a slightly more difficult problem involving segment trees
Code
- ⭐ Key Point: Operations with labels $0\to 2$
  - 0. Use $sum$ to reduce conditional judgments
  - 1. Update strategy for going up: pass in 3 parameters for convenience and for the merge strategy in line 88
  - 1. Merge strategy for querying: merge one node at a time, temporarily store the merged node in other variables, and then switch back
- [PS]
  - There is no need to handle interval modifications, so there is no lazy tag operation in this segment tree
  - According to the problem, $x>y$ needs to be handled specially