UPD: some video editorials on range query data structures: youtubePlaylist
Hello Codeforces, In this blog I will try to write a well detailed editorial for the CSES Range Queries section. The motivation for this editorial comes from https://codeforces.com/blog/entry/70018.
Quoting icecuber "I think CSES is a nice collection of important CP problems, and would like it to have editorials. Without editorials users will get stuck on problems, and give up without learning the solution. I think this slows down learning significantly compared to solving problems with editorials. Therefore, I encourage others who want to contribute, to write editorials for other sections of CSES."
So here I am writing an editorial for the range queries section.
If you find any error or maybe have a better solution to some problem please do share.
Range Sum Queries I
Given array is A[1..N], for each query of form (L,R) we need to output A[L] + A[L+1] + ... + A[R].
Define an array Prefix such that Prefix[i] = A[1] + A[2] + .. + A[i].
Prefix[R] = A[1] + A[2] + ... + A[R] and Prefix[L-1] = A[1] + A[2] + ... + A[L-1].
Consider Prefix[R] — Prefix[L-1] = (A[1] + A[2] + ... + A[R]) — (A[1] + A[2] + ... + A[L-1]) = (A[L] + A[L+1] + ... + A[R]).
So for every query simply output Prefix[R] — Prefix[L-1].
How Do I build the prefix Array.prefix[0] = 0
for i = 1 to N
prefix[i] = ar[i] + prefix[i-1]
Time complexity : O(N) to build prefix array and O(1) per query.
Range Minimum Queries I
Two possible ways are as follows :
1. Build a Range minimum query segment tree in O(N) time and answer each query in O(logN).
2. Build a sparse table in O(NlogN) time and answer each query in O(1).
Code for approach 1int small(int x,int y){return min(x,y);}
SegmentTree < int > rangeMinQueries(dataVector,INT_MAX,small);
For answering a query : rangeMinQueries.query(l,r)
Refer https://codeforces.com/blog/entry/71101 for my segment tree template.
Approach 2 : https://cp-algorithms.com/data_structures/sparse-table.html
Range Sum Queries II
So this one is a direct use of segment tree with point updates and I shall use my segtree template to answer this problem.
Codevector dataVector(n);
ll sum(ll x,ll y){return x+y;}
SegmentTree < ll > rangeSumQueries(dataVector,0,sum);
For query of type 1 : rangeSumQueries.update(idx,newVal);
For query of type 2 : rangeSumQueries.query(a,b);
Both of these queries can be performed in logN time.
Overall time complexity is O(N) for building segtree and QlogN for Q queries.
Range Minimum Queries II
Again a straightforward segment tree problem and I will use a similar code as I used for the previous problem. This is the same as RMQ1 except that here we also have point updates. Segment tree solution for RMQ1 and RMQ2 will be identical.
Codevector dataVector(n);
int small(int x,int y){return min(x,y);}
SegmentTree < int > rangeMinQueries(dataVector,INT_MAX,small);
For query of type 1 : rangeMinQueries.update(idx,newVal);
For query of type 2 : rangeMinQueries.query(a,b);
Both of these queries can be performed in logN time.
Overall time complexity is O(N) for building segtree and QlogN for Q queries.
Range Xor Queries
For this problem we can maintain a segment tree where each node of the tree will store the xor-sum of the range of elements for which it is responsible.
So root of the tree stores : A[1]^A[2]^....^A[N].
To calculate the answer for a particular interior node of the tree we do :
NODE_VAL = LEFT_CHILD_VAL ^ RIGHT_CHILD_VAL
For leaf nodes :
NODE_VAL = A[x], where [x,x] is the range this leaf node is responsible for and if x > N then NODE_VAL = 0 as 0 is the identity for xor_sum.
Again with these observations we can use the same segtree template as follows :
Codevector< int > dataVector(n);
int xor_sum(int x,int y) { return x^y; }
SegmentTree< int > xorSumQueries(dataVector, 0, xor_sum);
For answering the query : xorSumQueries.query(l,r)
AC code : https://ideone.com/mPhqas
Range Update Queries
Nice question which can be directly solved with a segment tree with lazy propagation but that is an overkill plus my segtree library does not support lazy propagation as of now.
Let's define a few terms:
SUM[i] = overall update done on the ith element till now
Initially SUM[i] = 0 for all i as no updates have yet been performed, now we would like to track the updates happening so that our answer to a query 2 k can easily be v[k] + SUM[k] where v is the initial array.
How to efficiently maintain the SUM array? Let us build a range sum query segment tree on some array X which has all elements initialized to 0.
DEFINE : RSQ[i] = X[1] + X[2] + .. + X[i] = rangeSumQuery(1,i)
Now say we have a query which tells us to add u to all elements in the range [l,r] then if I perform a point update and make X[l] = X[l] + u think what happens to RSQ[i] for different values of i.
RSQ[i] is unaffected for all i where i < l
and RSQ[i] = RSQ[i] + u for all i >= l.
Effectively we just did a range update on the abstract array RSQ and the range update is equivalent to adding u to all elements of array RSQ from l to N.
But we wanted the range update to be only for the range [l,r], so we should now do a range update in which we subtract u from [r+1,N] and this is the same as doing a point update to X[r+1] such that:
X[r+1] = X[r+1] — u
it must be easy to see the abstract array RSQ is nothing but the required SUM array.
So here is the algorithm :
For every range update query (l,r,u):
point_update(l,current_val + u)
point_update(r+1,current_val — u)
For every query -> value at pos idx:
print SUM[idx] + V[idx]
AC code : https://ideone.com/vBZpYx
Time complexity per query is logN.
Forest Queries
For every query of the form (x1,y1,x2,y2) we need to answer the number of trees inside the rectangle described by the top left cell of rectangle (x1,y1) and the bottom right cell of rectangle (x2,y2).
Define : DP[i][j] as the number of trees in the rectangle described by (1,1) and (i,j).
Can we use DP matrix to evaluate answers for every query?
Ok, but how?
Spoilerfirst please check this image : https://www.techiedelight.com/wp-content/uploads/Result.png
Trees in rectangle ((x1,y1),(x2,y2)) can be decomposed into the following rectangles :
1. Trees in rectangle ((1,1),(x2,y2)) = DP[x2][y2]
2. Trees in rectangle ((1,1),(x1-1,y2)) = DP[x1-1][y2]
3. Trees in rectangle ((1,1),(x2,y1-1)) = DP[x2][y1-1]
4. Trees in rectangle ((1,1),(x1-1,y1-1)) = DP[x1-1][y1-1]
Finally we have the answer to our query as DP[x2][y2] — DP[x1-1][y2] — DP[x2][y1-1] + DP[x1-1][y1-1]
How to build DP matrix?
Let tree[i][j] = 1, if there is a tree at cell (i,j) else tree[i][j] = 0.
DP[0][0] = DP[-1][0] = DP[0][-1] = 0
for i from 1 to N:
for j from 1 to N:
DP[i][j] = DP[i-1][j] + DP[i][j-1] — DP[i-1][j-1] + tree[i][j]
Time complexity for build O(N*N) and time complexity per query is O(1).
AC code : https://ideone.com/5dGTfY
Hotel Queries
Observation : For each group, we need to find the 1st hotel with enough vacancies and book rooms for the group in that hotel.
Brute force : Start checking every hotel from left to right for the number of rooms it has. As soon as you find a hotel with enough rooms use required number of rooms in this hotel. Repeatedly do this till all groups have been assigned a hotel.
How to optimize?Try thinking about the following problem instead, is there any hotel in the first x hotels which can be assigned to the current group?
Let us say we are able to answer this problem efficiently with a yes/no.
Then if the answer is yes, our problem reduces to finding the 1st hotel with enough rooms in the range [1,x] instead of the range [1,N].
if the answer is no, our problem reduces to finding the 1st hotel with enough rooms in the range [x+1,N] instead of the range [1,N].
So clearly, we can simply do a binary search to find the correct hotel and assign it to current group.
How do I know if there is any hotel in the first x hotels which can be assigned to the current group?
SpoilerLet current group size be G. Then if there exists a hotel in the first x hotels with vacancy >= G then our answer is YES else our answer is NO.
if (RANGE_MAX_QUERY(1,X) >= G) return YES else return NO.
Algorithm :
For each group gi with size si:
Find the 1st hotel x such that vacancy(x) >= si.
Do point update : vacancy(x) = vacancy(x) — si.
Print x.
If no valid x exists print 0.
Time complexity is O(Mlog^2N), logN steps for the binarySearch and each step of the binary search uses the Range max query segment tree which works in logN time.
List Removals
Brute force is quite simple if you simply simulate what is mentioned in the problem.
Let us try to optimize. So whenever we are asked to delete some xth element of the list we need to first locate the xth element, print it and then delete it.
How can we make the above processes faster?
Let us keep a boolean array PRESENT of size N and PRESENT[i] = 1 if the ith element of the list has not yet been deleted, 0 otherwise.
Now let us say we have the query : delete the xth element of the list, then this means we are going to delete the element at the jth index of the initial list such that :
- PRESENT[j] = 1.
- sum of PRESENT[i] for all i from 1 to j = x.
Why above conditions are necessary and sufficient to locate the correct element?
If are we deleting the element it has to be present in the list currently and so PRESENT[j] should be 1.
If this element at index j(of the initial list) is the xth element of the list(current state of the list) then there are exactly x elements present in the list in range [1,j](of the initial list) and remaining j — x elements got deleted in some previous queries.
How do I find this j?
Ok, elaborate.
SpoilerThe correct j lies in the range [1,N]. Is the index mid the correct index?
Consider following facts :
If number of elements not yet deleted in [1,mid] > x then search range should be updated to [1,mid-1] else If number of elements not yet deleted in [1,mid] < x search range should be updated to [mid+1,N].
else If number of elements not yet deleted from [1,mid] = x then if PRESENT[mid] = 1, mid is the correct index else update search range to [1,mid-1].
How do I find number of elements not yet deleted in the range [1,j]?
Hint : problem comes from range query sectionBuild a range sum query segment tree on the PRESENT array and find the sum of the range [1,j] in logN time.
Once you have found the correct j, you need to print it and also mark PRESENT[j] = 0 and make the required point update in the segment tree.
Time complexity analysis is similar to previous problem.
AC code : https://ideone.com/anpuXy
Salary Queries
Okay so, this seems a bit hard. Maybe if the max possible salary of the employees was limited to some smaller amount(instead of a billion) we might be able to solve it.
So try solving the problem under the constraint that p,a,b <= 10^7.
Now the problem is much easier if I maintain the number of people with a given salary, let us define
freq[i] : number of employees with the salary i
We may now build a range sum query segment tree on this array and to answer a query we simply calculate the sum of the range [a,b].
For updating the salary of some employee from x to y, we do the point updates freq[x] -= 1 and freq[x] += 1 because now 1 less employee has salary x and 1 more employee has the salary y.
But the problem is not solved, since we needed to do this for max possible salary = 1billion, but now we know how to do it for 10^7.
So lets group the salaries into 10^7 buckets and each bucket represent a range of 100 different contiguous salary values. The 0th bucket represents salaries from 1 to 100 and ith bucket represents the salaries from (i)*100 + 1 to (i+1)*100.
These buckets will store aggregated number of employees that have salaries in the given range represented by the bucket.
Now for query [a,b] : all the buckets that are entirely in the range [a,b] their aggregate values should be taken and summed up and for the 2 partial buckets(or 1) not entirely included in the range [a,b] we shall do a brute force.
So build a segment tree over the buckets and calculate the sum over all completely included buckets in the range [a,b]. For remaining partially included buckets do a brute force(actually iterate over approx 100 possible values and choose to include those which are required by a particular query, refer code).
A code will make this explanation much more clear.
AC code : https://ideone.com/zg97c8
Time Complexity?proportional to 10^7 operations to build the tree, per range sum query and per point update operations proportional to log(10^7). Accessing the map is proportional to logN operations, for left extreme and right extreme buckets we will need to do proportional to (logN + 100) operations.
Somewhat proportional to (10^7 + Qlog(10^7) + 200*Q + Q*logN) operations.
other way to do it is using a dynamic segment tree in which you only build a node of the tree when it is needed.
Distinct Values Queries
This is a direct application of the MO's Algorithm. You may read more about MO's algorithm on https://blog.anudeep2011.com/mos-algorithm/
The brute force can be done by simply iterating from index a to b and maintaining number of distinct elements seen till now and a frequency array to indicate which elements and how many occurrences of those elements is present.
Frequency[i] = count of occurences of i in the current range.
Next we try to build the required ADD and REMOVE functions which help MO's algorithm to function properly.
To ADD a new element in the current range simply check if this element is already present(frequency > 0) and if it is present just increase its frequency else if its frequency was 0 then make it 1 and also increase the number of unique elements in the range.
To REMOVE an element from the current range, decrement its frequency by 1, if its frequency reaches 0 then decrease the number of distinct elements in the current range.
After this sort the queries as described by MO's algorithm and you are done.
Twist : We cannot use frequency array as value of individual element can go upto 10^9. So what I'll simply use an unordered_map?
No, unordered_map solution will time out due to high constant factor involved.
How to continue using the frequency array?Coordinate compression, simply map larger values to smaller values in the range [1,N] and you are done as N can be atmost 2*10^5.
We can do this because we don't really care about the actual values but only about the number of unique values in a range.
Time complexity : O((N+Q)root(N))
AC code : https://ideone.com/RkC547
Subarray Sum Queries
Let us try to keep track of the max sum subarray in a particular range [L,R]. If we were to build a segment tree in which each node of the tree stores max sum subarray of the range that the node is responsible for then the root keeps track of max sum subarray in the range [1,N].
However for segment trees to be efficient we need to generate the answer of interior nodes of the tree using the answers/information provided by the child nodes.
Now let's try to generate the answer for some interior node P of the segment tree assuming that we already have the answers for the children of the node P.
Node P is responsible for the range [l,r], its left child is responsible for the range [l,mid] and its right child is responsible for the range [mid+1,r].
Now we need to find the sum of max sum subarray in the range [l,r].
Assume you have all necessary information about the child nodes but if you have some information about a child node you also need to generate that piece of information for the parent node as well(since this node also has a parent which will use information given by P to generate it's answer).
How to relate the answer for parent to the answers about children?Consider the following possibilities regarding max sum subarray in range [l,r]:
1. It might lie entirely in the range [l,mid] or entirely in range [mid+1,r].
2. It might be some subarray [p,q] such p <= mid and q > mid
Agreed, now what info to keep for every node?We need to cover all the possibilities discussed above.
If subarray lies entirely in [l,mid] then my subarray for [l,r] is the same as that for [l,mid] and so is the sum, so it is required to know the sum of max sum subarray of range [l,mid] and on similar lines we also need to know sum of max sum subarray of range [mid+1,r].
Now try and think what property is useful to calculate the maximum sum subarray [p,q] such p <= mid and q > mid.
The subarray [p,q] is the union of the subarrays [p,mid] and [mid+1,q]. Among all possible [p,mid] subarrays we should choose p(l<=p<=mid) such that sum of elements in range [p,mid] is maximized and similarly among all possible values of q(mid+1<=q<=r) we should choose q such that sum of elements in range [mid+1,q] is maximized, maximizing these two individually is equivalent to maximizing [p,q].
Call [p,mid] as the suffix and [mid+1,q] as prefix. Our max sum subarray [p,q] such that p <= mid and q > mid is nothing but (suffix_of_left_child) UNION (prefix_of_right_child).
So to summarize, for every node which represents the range [l,r] we should store :
1. sum of max sum subarray in the range [l,r].
2. maximum possible sum of some prefix [l,x] (such value of x is chosen, such that l <= x <= r and sum of elements in range [l,x] is maximum possible.)
3. maximum possible sum of some suffix [x,r].
We now know how to calculate sum of max sum subarray for some node using the above mentioned information about children nodes but as discussed we should also calculate prefix and suffix info for the parent also.
How to calculate prefix and suffix for parent nodeThe maximum sum prefix could be the same as prefix_of_left_child or it could be the entire left_child_range UNION prefix_of_right_child.
But now we need the sum of elements of left_child_range as well, which is the sum of all elements in [l,mid]. So this is another information we should store for every node.
Similarly the maximum sum suffix could be the same as suffix_of_right_child or it could be the entire right_child_range UNION suffix_of_left_child.
Refer the combine function in the code for more clarity.
AC code : https://ideone.com/MhVmBs
Time complexity : logN per update.
Forest Queries II
Problem is almost the same as Forest Queries but we also have point updates.
I will discuss two approaches, one of them is quite efficient while the other one struggles to run in the time limit(passes if constant factor is low).
Approach 1
Let us do build the same DP matrix which we had built for the problem Forest Queries. If somehow we are able to keep our DP matrix consistent with the updates then our answer will be the same as before.
ANSWER TO QUERY (x1,y1,x2,y2) : DP[x2][y2] — DP[x1-1][y2] — DP[x2][y1-1] + DP[x1-1][y1-1]
How to efficiently track the updates that happen on some entry DP[i][j]?
Which entries of the DP matrix change if cell (i,j) is updated?DP[x][y] represents the number of trees in the rectangle described by ((1,1),(x,y)).
Only those entries will be affected which contain the cell (i,j). If the rectangle described by ((1,1),(x,y)) contains the cell (i,j) then we have the following conclusions about x and y :
1. x >= i
2. y >= j
What will be the change in these entries?
Either a +1 or a -1, depending upon whether a tree was planted or removed in cell (i,j).
Alright, so now I need to efficiently add or subtract 1 from all the matrix entries (x,y) where that x >= i and y >= j.
So how do we track these updates?Range query Data structures.
We needed to either add or subtract 1 from all entries (x,y).
Now consider the row X(X >= x) : for this row we need to update entries (X,j), (X, j+1) ... (X,N)
This is nothing but a range update to the range [j,N].
So here is what we can do, keep a fenwick tree for each row. Fenwick[k] represents the fenwick tree for the kth row and Fenwick[k].rangeSum(0,j) represents the net change for the entry (k,j).
For updates, simply do the point updates Fenwick[k].update(j, delta) for all k from i to N where delta is either 1 or -1.
Time complexity O(Q*N*logN)
AC code : https://ideone.com/mcAdwL
Code for fenwick tree is taken from : https://cp-algorithms.com/data_structures/fenwick.html
Approach 2
This approach is more efficient and some might also find it easier to understand.
It uses a 2D Binary Indexed tree to achieve an overall time complexity of O(N^2 + Q*log^2(N)).
You can read more about it here : TopCoder-2DBIT
Range Updates and Sums
No surprises here. My solution will use the data structure and the technique related to that data structure which most would have already guessed after reading the problem statement. The important thing would be a thorough understanding of the concept and a neat implementation(I have tried to make it readable).
what data structure, what technique?We will use a segment tree with lazy propagation. If you have an alternate approach, please share.
Alright so our segment tree needs to support the following operations :
1. increase values in range [l,r] by x.
2. set values in range [l,r] = x.
3. return sum of values in range [l,r].
Think about what information should we store per node of the tree, so that we are able to lazily update our nodes when a new update comes in and we are able to propagate the updates downward when needed.
To better understand lazy propagation, I recommend reading this : Super amazing theory in 1 comment (My implementation uses applyAggr and compose functions mentioned here).
What info to store per node?Ofcourse both the updates are needed to be stored along with the sum, what do they represent?
Let's keep the following variables per node:
1. setAll
2. increment
3. Sum : The sum of the values in range [l,r](the range represented by the node)
Representation : All the values in range [l,r] should be set to the value "setAll" and then their values should be increased by "increment". Initially, we may set increment to 0 but then what about setAll? if we set setAll to 0 it would mean all values are 0. So we need an indicator that tells if the value given by setAll is valid or invalid.
So let us also keep another variable setAllValid per node which is 1 if the value given by setAll is valid otherwise 0.
How do I find the actual Sum using these variables?if setAll is valid, finding sum is quite easy. If L is the number of elements in the subarray which this node represents then our sum will simply be L * (setAll + increment).
if setAll is invalid, then whatever is the value of the sum variable we should add (L * increment) to it.
How do i propagate these updates downward?First apply them to the node and calculate the sum for this node.
Next push the updates down to the children.
Now the child nodes may have updates of their own as well, how to combine these updates?
Updates propagated down are always more recent.
So if parent node had setAllValid = 1, then all updates in child node are overwritten by the parent update values otherwise the increment of parent and increment of child node summed up make the new increment of the child node and rest everything stays same.
Also after you have pushed the updates down, you may reset the updates of the parent back to default values(increment = 0, setAllValid = 0)
Time Complexity is logN per query.
If something is not explained or if something isn't clear feel free to ask but I recommend understanding lazy prop well before attempting the problem or reading the editorial.
AC code : https://ideone.com/8HQxMk
Please feel free to point out mistakes, suggest better/alternate solutions and to contribute.
I'd be glad to know if this helps :)
P.S. Will add remaining problems in a few days.
UPD : Editorial is almost complete with 2 problems left. 2nd last uses segment tree with lazy prop and I am guessing the last one uses some kind of persistent data structure, will add soon.