Arrays and searching 0/120

Fenwick trees for prefix sums and updates · 3 of 3 Advanced

Coordinate compression

Index a Fenwick tree by value instead of by position, replacing large values by their ranks among the values that occur.

1,727 words · 8 min read

Part 1 of 4 A tree indexed by value

Count the values between two bounds

So far a position in the tree was a position in the array. Some questions are about the values themselves, such as how many of them lie between two bounds. For those, the tree is indexed by value.

A company has nn employees, numbered from 1, and employee ii starts with the salary pip_i. Process qq queries: ! k x changes the salary of employee kk to xx, and ? a b asks how many employees earn at least aa and at most bb.

The first line holds nn and qq, the second the nn salaries, and each further line one query. Print the answer to every ? query.

Constraints

  • 1≤n,q≤2⋅1051 \le n, q \le 2 \cdot 10^5
  • 1≤pi,x≤1091 \le p_i, x \le 10^9
  • 1≤k≤n1 \le k \le n
  • 1≤a≤b≤1091 \le a \le b \le 10^9

Sample · Input

5 3
3 7 2 2 5
? 2 3
! 3 6
? 2 3

Output

3
2

In the sample, three employees earn between 2 and 3 at first: the salaries 3, 2 and 2. Then employee 3 moves from 2 to 6, and two are left.

Checking every employee for each ? query costs nn comparisons per query, up to 4×10104 \times 10^{10} at these limits.

Suppose for a moment that salaries are small, as in the sample, where the largest is 7. We can keep an array count in which count[s] is the number of employees who earn exactly s:

The index is a salary. Two employees earn 2, and one each earns 3, 5 and 7. The highlighted cells are the ones ? 2 3 adds.

The query ? 2 3 is count[2] + count[3], which is 2+1=32 + 1 = 3: a range sum over count. The query ! 3 6 moves employee 3 from salary 2 to salary 6, so it subtracts 1 from count[2] and adds 1 to count[6], which is two point updates. An array with point updates and range sums is what a Fenwick tree stores, so count goes in a tree. The program also keeps the current salary of each employee in a plain array, to know which count to lower.