CODEWITHSUNDEEP
algorithmdata-structures
Raghav James
Raghav James

Reputation: 57

Range Update and Query on array

I have updates and queries on array A having n elements.
I have two types of queries :
type 1 (Update) : Given x, decrement the value of all elements in array A whose value is greater than or equal to x.
type 2 (Query) : Given (l, r, x), find the xth smallest element in array A whose value lies between l and r (both inclusive).

I could come up with no better solution other than brute force which could be as expensive as O(q*n). Is there any optimal solution ? Elements of array A could be as large as 10^18.

Upvotes: 2

Views: 850

Answers (2)

Sneftel
Sneftel

Reputation: 41542

The data structure I'm thinking of is an augmented variant of a self-balancing binary tree, such as an AA-tree. In addition to the normal members, each node also stores a count of decrements which are implicitly applied to its descendants. Rather than ever change the numbers themselves, to see the final value of a node you subtract the decrement count from each of its ancestor nodes. Each node also maintains a count of its descendants.

An update consists of a bound search through the tree (complexity O(log n)), and incrementing the decrement count of O(log n) nodes. In some cases you will also have to move elements just below the bound into that tree (because they're no longer smaller than all the elements, thanks to the decrement), which is also O(log n). (Note that there's a bit of tricky descendant-updating needed for that last bit, but I don't think it blows the overall bound.)

The "query" operation is straightforward; binary search to find l (r doesn't matter to the operation, AFAICT) then use the descendant-count to accelerate finding the k-th smallest in that range to O(log k).

So both operations have time O(log n), and total time is O(q*log n), assuming you don't count the O(n*log n) time to build the initial tree.

Upvotes: 1

MrDeal
MrDeal

Reputation: 373

There is no better solution than running each of the described queries in faster than O(n), where n is the number of the elements of your array, consistently on an unsorted array as you describe your problem. That is because you have to consider each element in the array for your queries. The issue is that you have no information on your data, thus you will never know where to check to make things faster.

If you will make a lot of queries you can possibly make some optimisation by sorting your array and keeping it sorted. While sorting will take O(n log(n)) initially (Quicksort, Mergesort) it will allow you to perform Query in O(log(n)) (or worst case O(n)) using a modified Binary Search (Find the first smallest element in your range and then take the next x elements). (If you use a library sort like qsort you will sort in something like 1.3 nlog(n), which is really good)

It will also allow you to perform your Update quicker, since again you can use BSearch to get to the values you are looking for. Here knowledge about the data is important. If your decrement will not change the order a lot (check the border case elements) then this is more efficient in the long run.

If your array is sorted, you can also efficiently sort after Q1 by just considering the elements to the left of your first element larger or equal to x. If some of these elements is now larger than some of your elements that where decremented you can find the border between them and do a swap between the smaller and larger areas after Q1 (smart sorting, using the information you have on your data).

If you must not sort your data (for graphing purposes or so) then linear time is the best you can hope for. Also sorting is not necessary if your array is small, it will be overkill not bring noticeable improvements. And honestly, linear time is really good on modern computers.

Upvotes: 0

Related Questions