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 employees, numbered from 1, and employee starts with the salary . Process queries: ! k x changes the salary of employee to , and ? a b asks how many employees earn at least and at most .
The first line holds and , the second the salaries, and each further line one query. Print the answer to every ? query.
Constraints
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 comparisons per query, up to 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:
? 2 3 adds.The query ? 2 3 is count[2] + count[3], which is : 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.
Replace each salary by its rank
Real salaries go up to . A tree with a cell for every possible salary would need cells, which is 8 GB at 8 bytes a cell, and almost all of them would stay 0. At most different salaries ever occur: the starting ones and one new one for each ! query.
So only the salaries that occur get a position in the tree. The program reads every query before it answers any, which is called answering offline. It collects the starting salaries and every salary that a ! query sets, sorts them and removes the duplicates. The rank of a salary is its place in that sorted list, counted from 1, and the rank is its position in the tree. Replacing values by their ranks is called coordinate compression. For the sample:
! 3 6. The highlighted cells are the ones ? 2 3 adds.Salary 6 has a rank although nobody earns it at the start, because the ! query sets it later. Ranks are in the same order as the salaries, so the salaries between two bounds still occupy a range of neighbouring positions: salaries 2 to 3 are ranks 1 to 2.
The bounds and of a ? query can be any numbers, so they may not be in the list and may not have a rank. The query uses two counts over the sorted list instead: how many listed salaries are at most , and how many are less than .
If of the listed salaries are at most , those salaries have the ranks 1 to , so prefix(c) is the number of employees who earn at most . In the same way, if of the listed salaries are less than , prefix(d) is the number of employees who earn less than . The answer is prefix(c) - prefix(d), and both counts come from a binary search:
bisect_right(values, b) returns the number of entries of the sorted list values that are at most b, and bisect_left(values, a) returns the number that are less than a.
For ? 2 3 on the sample, two listed salaries are at most 3 and none is less than 2. The answer is prefix(2) - prefix(0), which is before the change and after it.
input = sys.stdin.readline
def prefix(tree, i): # sum of positions 1..i
total = 0
while i > 0:
total += tree[i]
i -= i & -i
return total
def add(tree, i, delta): # add delta at position i
while i < len(tree):
tree[i] += delta
i += i & -i
n, q = map(int, input().split())
salary = [0] + list(map(int, input().split())) # salary[k]: employee k now
queries = [input().split() for _ in range(q)]
values = sorted(set(salary[1:]) | {int(x) for kind, _, x in queries if kind == "!"})
rank = {v: i + 1 for i, v in enumerate(values)} # salary -> tree position
tree = [0] * (len(values) + 1)
for s in salary[1:]:
add(tree, rank[s], 1)
out = []
for kind, a, b in queries:
a, b = int(a), int(b)
if kind == "!": # employee a now earns b
add(tree, rank[salary[a]], -1)
salary[a] = b
add(tree, rank[b], 1)
else: # how many earn from a to b
out.append(prefix(tree, bisect_right(values, b)) - prefix(tree, bisect_left(values, a)))
print("\n".join(map(str, out)))On the sample input the program prints 3 and 2.
Python details
rank is a dictionary from each listed salary to its tree position. It is used only for salaries that someone earns, which are always in the list. The bounds of a ? query go through bisect_right and bisect_left.
Count salaries by rank
In this widget the positions are the five ranks, and each holds the number of employees with that salary before ! 3 6. A prefix sum at rank 2 reads cell 2, which covers ranks 1 and 2, and gives , the first answer.
To replay ! 3 6, set the operation to Point add and add at rank 1, for salary 2, then at rank 4, for salary 6. A prefix sum at rank 2 then reads 2.
Cost of a tree indexed by value
- Checking every employee
per?query - Up to 200,000 comparisons for one query, for 200,000 queries.
- Compressing
, once - Sorting the salaries that occur.
- Converting a bound
- One binary search in the sorted list.
- A change or a count
- Two point adds or two prefix sums over positions.
- Memory
- The sorted list and cells, at most 400,001, in place of .
Count inversions with a tree indexed by value
The salary tree counted values in a range while the values changed. The same tree is used on arrays that never change, by adding the values to it one at a time during a pass over the array. One example is counting inversions. An inversion is a pair of positions where the earlier value is greater than the later one. This array has four: 5 before 2, 5 before 1, 2 before 1 and 6 before 1.
Comparing every pair takes comparisons, about for 200,000 values. With a tree indexed by value, we go through the array from left to right and ask at each value x how many of the values before it are greater. The tree holds a count for each value seen so far, so prefix(x) is the number of earlier values that are at most x. The earlier values that are greater than x are all the others:
After the lookup we add 1 at x, so that later values count it. As with the salaries, values that can be large are first replaced by their ranks, and the tree is indexed by rank. The ranks of 1, 2, 5 and 6 are 1, 2, 3 and 4:
| Value | Rank | Values seen so far | prefix(rank) | Earlier values that are greater |
|---|---|---|---|---|
| 5 | 3 | 0 | 0 | 0 |
| 2 | 2 | 1 | 0 | 1 |
| 6 | 4 | 2 | 2 | 0 |
| 1 | 1 | 3 | 0 | 3 |
The last column adds up to 4. When an earlier value equals the current one, prefix of the current rank includes it and the subtraction leaves it out. That is the right result, because two equal values do not form an inversion.
def prefix(tree, i): # sum of positions 1..i
total = 0
while i > 0:
total += tree[i]
i -= i & -i
return total
def add(tree, i, delta): # add delta at position i
while i < len(tree):
tree[i] += delta
i += i & -i
def count_inversions(nums):
values = sorted(set(nums))
rank = {v: i + 1 for i, v in enumerate(values)} # value -> tree position
tree = [0] * (len(values) + 1)
inversions = 0
for seen, x in enumerate(nums): # seen: how many values came before x
inversions += seen - prefix(tree, rank[x])
add(tree, rank[x], 1)
return inversions
print(count_inversions([5, 2, 6, 1]))
print(count_inversions([3, 3, 1]))The second call has two equal values. Its two inversions are the pairs that each 3 makes with the 1, and the two 3s are not counted as a pair. The pass makes one prefix sum and one point add per value, about 400,000 tree operations for 200,000 values.
Changing the direction of the pass or the lookup answers related questions. Going through the array from right to left and reading prefix(rank - 1) gives, for each position, the number of smaller values after it, which is what Count of Smaller Numbers After Self in the problem list of this page asks for.
Common coordinate compression mistakes
Compressing only the starting salaries.
- Where it breaks
- On the sample, 6 is then missing from the sorted list and has no rank. The Python program stops with
KeyErroratrank[6]. The C++ program'supto(6)returns 3, the rank of salary 5, so employee 3 is counted as earning 5. If the input then asked? 5 5, the program would print2instead of1. - The fix
- Read every query first, and compress the starting salaries together with every salary that a
!query sets.
Counting the salaries less than for the upper bound.
- Where it breaks
- For
? 2 3, one listed salary is less than 3, so the count stops at rank 1 and the query prints2instead of3. The employee who earns exactly 3 is left out. - The fix
- Count the salaries that are at most for the upper bound, and the salaries that are less than for the lower one.
Adding the current value to the tree before its lookup in the inversion count.
- Where it breaks
- On
[5, 2, 6, 1]each lookup then counts the current value itself, every step is 1 too low, and the total is0instead of4. - The fix
- Look up first, then add 1 at the rank of the current value.
Recall Before `! 3 6`, what does `? 4 6` print, and which two prefix sums give it?
It prints 1. The sorted list is 2, 3, 5, 6, 7. Four of its salaries are at most 6 and two are less than 4, so the answer is prefix(4) - prefix(2), which is : the one employee who earns 5. Rank 4, for salary 6, still counts nobody.