Hey Codeforeces! How are y'all doing? I was solving the CSES Range Queries module and thought of sharing my solutions with you if it's of any use. This blog entry is motivated by kartik8800's own entry (https://codeforces.com/blog/entry/77128). I noticed it was missing some of the last problems of the list, so I thought of adding those here as well.
This is my first blog entry, so don't mind to correct me if you notice anything odd in here. If you have any alternative solutions to these problems, it'd be great to share them as well!
Static Range Sum Queries
Given an array, answer $$$q \leq 2\cdot10^5$$$ queries consisting on the sum of values in the subarray $$$[l, r]$$$.
Let's obtain the answer of a single query from the precalculated sum of every prefix in the array. This technique is called prefix sum. This approach allows us to answer each query in $$$O(1)$$$.
My solution: https://cses.fi/paste/32b8635571e24e677bbbda/
Static Range Minimum Queries
Given an array, answer $$$q \leq 2\cdot10^5$$$ queries consisting on obtaining the smallest value in the range $$$[l, r]$$$.
This problem needs a data structure known as Segment Tree, which consists on dividing a range into two from the middle, constructing the answer of the parent node from the answer of its children. This allow us to construct the structure in $$$O(n)$$$ or $$$O(n \, log \, n)$$$, depending on the implementation, and answer each query in $$$O(log \, n)$$$.
Check out this explanation, which is better explained than what I could: Segment Tree — CP Algorithms
My solution: https://cses.fi/paste/8fbbac3c0e58b2da7bbc89/
Dynamic Range Sum Queries
Given an array, process $$$q \leq 2\cdot10^5$$$ queries which can be of two types:
- Update the value at position $$$k$$$ to $$$u$$$.
- Find the sum in range $$$[l, r]$$$.
This problem also requires a Segment Tree. Though this one requires the ability to update an element. This allows us to process each query, of both types: update and sum, in $$$O(log \, n)$$$.
My solution: https://cses.fi/paste/a4b40b35c8a1fbba7b9bb6/
Dynamic Range Minimum Queries
Given an array, process $$$q \leq 2\cdot10^5$$$ queries which can be of two types:
- Update the value at position $$$k$$$ to $$$u$$$.
- Find the minimum value in range $$$[l, r]$$$.
This problem has the exact same solution as the previous one, with the very slight difference of changing a sum to a minimum. The way you update or query stays the same, though.
My solution: https://cses.fi/paste/cfa3d161f68e804d7be5ba/
Range Xor Queries
Given an array, answer $$$q \leq 2\cdot10^5$$$ queries consisting on the sequential bitwise xor done in range $$$[l, r]$$$.
This is, guess again, another Segment Tree without any additional observation. Just do an xor instead of a sum or a minimum or maximum.
My solution: https://cses.fi/paste/b1dd777466aac3f17bbd23/
Range Update Queries
Given an array, process $$$q \leq 2\cdot10^5$$$ queries which can be of two types:
- Increase each value in range $$$[l, r]$$$ by $$$u$$$.
- Find the value at position $$$k$$$.
This problem can be solved with two different structures: a Binary Indexed Tree (also known as Fenwick Tree) or a Segment Tree with a special feature called Lazy Propagation. I will explain my solution using a BIT. Don't worry, as there are some problems afterwards that will require the use of Lazy Propagation.
A BIT, in very basic terms, is a structure that is capable of storing and updating a prefix sum in $$$O(log \, n)$$$, dividing each prefix in ranges sized to powers of two. I personally love this structure, as it is very simple to programme and uses very cool ideas. You can check out this explanation on how it works: Fenwick Tree — CP Algorithms.
My solution: https://cses.fi/paste/ac29ce892d52e1cb7bc2bb/
Forest Queries
Given a boolean matrix of $$$n \cdot n$$$ ( $$$n \leq 1000$$$ ), answer $$$q \leq 2\cdot10^5$$$ queries consisting on the sum of all ones in a given rectangle between coordinates $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$.
This works very similarly to the Static Range Sum Queries problem. We will build a prefix sum matrix and obtain our answers from there.
My solution: https://cses.fi/paste/2bfff4ba202881fd7bc2f2/
Hotel Queries
Given an array of hotels, being $$$h_i$$$ the amount of rooms in each hotel, assign $$$m \leq 2\cdot10^5$$$ queued groups to a hotel, where $$$r_i$$$ is the numbers of rooms needed for each group. You will assign to a group the first hotel that has enough rooms for it.
We will need to do maximum queries to the array, as well as updating elements in it, considering the fact of each hotel room count to decrease in $$$r_i$$$ every time we assign a group to it. A Segment Tree seems suitable for that.
My solution: https://cses.fi/paste/46d52021e352417e7bdd54/
List Removals
Given an array, we will need to erase elements in a certain order given by the judge. We will need to output the values of those elements in the order they were removed. Notice that the indices of some elements will change once we remove some element.
The key observation to solve this is to understand how the indices change once we remove an element. If we remove the element at $$$i$$$, every element after $$$i$$$ will decrease its index by $$$1$$$, as each of those moves one position backwards. We can use a BIT to keep track of the updated positions every time we remove an element.
My solution: https://cses.fi/paste/d2d1539f965dacbb7be0bd/
Salary Queries
Given an array, process $$$q \leq 2\cdot10^5$$$ queries which can be of two types:
- Change an element at $$$k$$$ to $$$x$$$.
- Find the number of elements with values between range $$$[l, r]$$$.
Instead of manipulating the actual array to find the answers, we will use another structure to keep track of the frequencies of each value in it, and then do sum queries to that structure. Both a BIT or a Segment Tree are suitable for this.
Notice that given the constraints ( $$$p_i, a, b \leq 10^9$$$ ) we will not be able to fit a frequency array, as it will exceed the memory limit. We need what is called coordinate compression. This simply consists on casting every given value into smaller ones, preserving their properties, knowing that between all values in both the array and the queries there will be no more than $$$6 \cdot 10^5$$$ distinct values.
My solution: https://cses.fi/paste/22e03bc55df545c57ff025/
Prefix Sum Queries
Given an array, process $$$q \leq 2\cdot10^5$$$ queries which can be of two types:
- Update an element at $$$k$$$ to $$$u$$$.
- Find the maximum relative prefix sum in the subarray found in range $$$[l, r]$$$.
To solve this problem, we will need to keep track of not the elements in the array themselves, but the ones found in the prefix sum of it. We will also need to do maximum queries, then our ideal tool is a Segment Tree. We will need to do range updates, though. Here's where Lazy Propagation comes to place. Check out how this works: Range updates (Lazy Propagation) — CP Algorithms.
My solution: https://cses.fi/paste/b1d841b3cbff747b7ff277/
Pizzeria Queries
Given a list of building selling pizza, where $$$p_i$$$ is the price for a pizza in each building, process $$$q \leq 2\cdot10^5$$$ queries which can be of two types:
- Change the price for a pizza in building $$$k$$$ to $$$x$$$.
- Find the minimum cost for a pizza if you are in building $$$k$$$.
A cost for a pizza in building $$$k$$$ if you are in building $$$i$$$ is defined as $$$p_i + |i - k|$$$.
This problem requires us to look at how the answer will be seen depending on which building do we choose. If the building $$$k$$$ is before $$$i$$$, this means $$$k < i$$$, the answer will be $$$p_k + (i - k)$$$. The same way, if the building $$$k$$$ is after, this means $$$i < k$$$, the answer will be $$$p_k + (k - i)$$$.
Now, when we query, we know that $$$i$$$ will be a constant in our answer. This leads us to store our values in two different ways:
We will need two RMQ (Range Maximum Queries) Segment Trees: left and right, each of those with the values stored as described. And our answer will look as follows:
max(left.query(1, i) + i, right.query(i, n) - i)
My solution: https://cses.fi/paste/2af6ffade31059da83ed99/
Subarray Sum Queries
Given an array, proces and answer $$$m \leq 2\cdot10^5$$$ updates which will change some value in the array. After each update, answer the maximum sum found between any possible subarray.
This problem can be solved using a Segment Tree once you do some observations.
My solution: https://cses.fi/paste/83cca4e4c3d1caad85c185/
Distinct Value Queries
Given an array, answer $$$q \leq 2\cdot10^5$$$ queries which are defined as the number of distinct values in range $$$[l, r]$$$.
We will move away a little bit from logarithmic solutions, ans use another approach based on square root decomposition. This problem is a direct implementation of the Mo Algorithm. Again, we will need coordinate compression to fit these values in a frequency array. Check out how Mo works: Mo's Algorithm — CP Algorithms
My solution: https://cses.fi/paste/9e0c9a2d8ae9185e87c73f/
Increasing Array Queries
Given an array, answer $$$q \leq 2\cdot10^5$$$ queries which are defined as the minimum number of operations needed to make a subarray in range $$$[l, r]$$$ increasing, where an operation consists on choosing an index $$$i$$$ and increase its value by $$$1$$$.
The idea to the problem is to know, in the updated increasing subarray, which numbers are in it along with their frequencies. In other words, we will need the sum of both the updated and original subarray. The difference between both sums will be our answer.
My solution: https://cses.fi/paste/cdfd3130368426ab87e802/
Forest Queries II
This problem is the same as the one in Forest Queries I, with the slight difference of having some queries that will update some positions in our matrix.
We can work with a similar concept as with the first one, but with the ability to quickly update the suffixes of the matrix. We can use a BIT in 2D to do this job. a 2D BIT is just a BIT in which every element of it is another BIT. Therefore, we can perform operations in $$$O(log^2 \, n)$$$.
My solution: https://cses.fi/paste/ffe17526bd06c6bb87ed4f/
Range Update and Sums
Given and array, process $$$q \leq 2\cdot10^5$$$ queries which can be of three types:
- Increase each element in range $$$[l, r]$$$ by $$$x$$$.
- Set each element in range $$$[l, r]$$$ to $$$x$$$.
- Find the sum of the subarray in range $$$[l, r]$$$.
This is simply a Segment Tree with Lazy Propagation. You just have to be careful on how to do the updates, as every type 2 query will overwrite any other update stored in a node.
My solution: https://cses.fi/paste/61cbf01db11bfa6a8827de/
Polynomial Queries
Given an array, process $$$q \leq 2\cdot10^5$$$ queries which can be of two types:
- Update each element in range $$$[l, r]$$$ increasing the first element by $$$1$$$, the second by $$$2$$$, the third by $$$3$$$ and so on.
- Find the sum of the subarray in range $$$[l, r]$$$.
This problem is tricky, as it needs to do some math, at least for the way I solved it. But once you find the idea, you will be able to use a Segment Tree with Lazy Propagation.
So, lets do some math!
The overall sum for the whole range will be the sum from $$$1$$$ to $$$k$$$, being $$$k$$$ the size of the subarray. If we remember, that sum is defined as:
\begin{equation} \sum_{i=1}^k i = \frac{k(k + 1)}{2} \end{equation}
But what if we split that into our two child nodes? We will have our sum divided into two different expressions. Imagine the sum splits at position $$$m$$$. We will now have two sums, which are:
\begin{equation} \sum_{i=1}^m i \qquad \sum_{i=m+1}^k i \end{equation}
As we explore our Segment Tree downwards, we realize we will have to increase a node by a function consisting on the sum of $$$k$$$ consecutive numbers starting from $$$x$$$.
\begin{equation} f(k, x) = \sum_{i=0}^{k-1} x+i \end{equation}
\begin{equation} f(k, x) = x + (x+1) + (x+2) + ... + (x+k-1) \end{equation}
\begin{equation} f(k, x) = kx + (1 + 2 + 3 + ... + k-1) \end{equation}
\begin{equation} f(k, x) = kx + \frac{k(k-1)}{2} \end{equation}
This works well until we update our last node and store the update to be pushed afterwards. In the end, we will have a variable that contains the accumulation of a bunch of functions $$$ f(k, x_1) + f(k, x_2) + f(k, x_3) + ... $$$ How do I split that sum to push it into the node's children? Imagine the previous example:
\begin{equation} f(k, x_1) + f(k, x_2) + f(k, x_3) \end{equation}
\begin{equation} \left(kx_1 + \frac{k(k-1)}{2}\right) + \left(kx_2 + \frac{k(k-1)}{2}\right) + \left(kx_3 + \frac{k(k-1)}{2}\right) \end{equation}
\begin{equation} k(x_1 + x_2 + x_3) + 3\frac{k(k-1)}{2} \end{equation}
We can easily find the sum of all $$$x_1 + x_2 + x_3 $$$ only if we keep track of how many times an update was stored in the node (in this case 3), which can be easily stored too. Let's say we have $$$u$$$ updates queued in the node and our stored accumulated sum of functions is $$$y$$$.
\begin{equation} (x_1 + x_2 + x_3 + ...) = \frac{y — u\frac{k(k-1)}{2}}{k}\end{equation}
If we want to know by how many do we have to increase the left child of size, let's say $$$t$$$, simply replace $$$k$$$ from this same expression. If we want to know the one for the right node, simply subtract these two expressions.
\begin{equation} left = t(x_1 + x_2 + x_3 + ...) + u\frac{t(t-1)}{2}\end{equation} \begin{equation} right = y — left \end{equation}
This is the whole thing. Keeping this in mind you just have to execute your updates as you usually should.
My solution: https://cses.fi/paste/c856fba54576dd8b882c66/
Range Queries and Copies
This is definitely my favourite problem in this list, as it has an awesome and very creative solution I enjoyed a lot finding. Hope you like it as well.
You will keep track of a list of arrays, originally with only one array. Process $$$q \leq 2\cdot10^5$$$ queries which can be of three types:
- Set the value $$$i$$$ in array $$$k$$$ to $$$x$$$.
- Find the sum of the subarray in range $$$[l, r]$$$ in array $$$k$$$.
- Copy the array $$$k$$$ and append the copy at the end of the list.
My solution: https://cses.fi/paste/1521653b50707502883378/
