Permutacja - An Exercise in Range Query - Part I
Post date: Jan 14, 2013 9:33:06 PM
of up to elements, each with a value between and . There will be up to incremental modifications to the array, where a modification changes the value of one element. At every point in time, you must print whether the array admits a permutation
of the elements such that for , .
The naive solution would be to, after every modification, sort the array and see if the condition holds. This has complexity
, which is obviously too slow. The observation that only one element changes and thus must be resorted brings it down to
, but what we really need is an algorithm with runtime The main observation needed is to see that the condition can be satisfied if and only if there is at least one element in
greater than , at least two elements greater than ... and at least
elements greater than . Then, consider the array where . The original condition that the array admits a valid permutation then is equivalent to the condition that all elements of
are non-negative, or in other words .
The two operations we need to support on this array is to query for its minimum, and to add a value to every element in a range. Indeed, if we change a value in
from to , then we'd like to call something like add(c, 0, x-1, -1); add(c, 0, y-1, 1); because when we remove x, then for
the number of elements greater than i decreases by 1, and then similarly when we insert y.
Hopefully you now immediately think of a range query type data structure, like a binary-indexed tree or a segment tree. Aram has a nice tutorial about them, and so does TopCoder (BIT, Segment Tree). I will focus on the segment tree approach to this problem. It may be possible to do this with 2 BITs, but I don't know how.
So, the basic structure of the algorithm is clear. First, set up the array
with the original data, then as you read in each modification run the two update steps, query for the minimum, and output TAK or NIE based on whether the minimum is non-negative.
But will this run in time? The cost of the query is logarithmic at worst (actually, for us, since we always want the minimum of the whole tree, this can be optimized to be constant time). But what about the cost for the updates? Thinking about it carefully, doesn't range queries assert time
for updating a single element, so wouldn't updating a range of possibly up to n elements take
time? Well, it turns out that if you update all of the elements in the range first, and then propagate it down the tree all at the same time, it is actually per range update. That, however, is still too slow...
In Part II I will explain what lazy propagation in segment trees are, and how to use lazy propagation to solve this, and many other problems that require range-update and range-query, in amortized logarithmic time per query and update.