Maaxle's blog

By Maaxle, 9 months ago, In English

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.net/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)$$$.

How to obtain the answer from prefixes?
How to build the prefix sum?

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

How to find the minimum (or maximum) of a range in a Segment Tree?

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:

  1. Update the value at position $$$k$$$ to $$$u$$$.
  2. 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)$$$.

How do I update an element?

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:

  1. Update the value at position $$$k$$$ to $$$u$$$.
  2. 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.

What is a bitwise Xor?

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:

  1. Increase each value in range $$$[l, r]$$$ by $$$u$$$.
  2. 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.

How to do range updates in a BIT?

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.

How to find prefixes in a matrix?
How do I find the sum of a rectangle from those prefixes?

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.

How to find the first element mayor or equal to rᵢ?

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.

How to find the real position of an element using its updated index?

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:

  1. Change an element at $$$k$$$ to $$$x$$$.
  2. 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:

  1. Update an element at $$$k$$$ to $$$u$$$.
  2. 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.

How does our answer look with this approach?

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:

  1. Change the price for a pizza in building $$$k$$$ to $$$x$$$.
  2. 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:

$$$p_k + k$$$
$$$p_k - k$$$

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.

How do I find the answer of a node from its children?

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

Note (if you struggle with this solution to fit)

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.

Hint 1: What elements are replaced, by which other are they replaced and in what conditions?
Hint 2: The answer is part of something bigger?
The whole solution: Use those two hints together!

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:

  1. Increase each element in range $$$[l, r]$$$ by $$$x$$$.
  2. Set each element in range $$$[l, r]$$$ to $$$x$$$.
  3. 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.

But plase, don't over complicate yourselves and end up with something as shameful as this XD:

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:

  1. Update each element in range $$$[l, r]$$$ increasing the first element by $$$1$$$, the second by $$$2$$$, the third by $$$3$$$ and so on.
  2. 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:

  1. Set the value $$$i$$$ in array $$$k$$$ to $$$x$$$.
  2. Find the sum of the subarray in range $$$[l, r]$$$ in array $$$k$$$.
  3. Copy the array $$$k$$$ and append the copy at the end of the list.
Hint 1: Which updates do we care about?
Hint 2: A timeline!
The whole solution

My solution: https://cses.fi/paste/1521653b50707502883378/

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Pretty useful, thank you. :D

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Underrated blog tbh.

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Prefix Sum queries can also be done without Lazy Propagation.

I have done Prefix Sum queries by merging solutions from child nodes The logic is quite similar to Maximal segment in array problem

Each node of a segment tree will maintain two things:
1. max pref sum of its range
2. sum of all elements of the range.

Merge logic will be simple Lets say we have two child nodes left and right Max prefix sum of the range can be
(i) Max prefix sum of the left children
(ii) Total sum of elements of the left child node + max pref sum of right child
we will choose maximum of i and ii

Code
»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hotel Queries can be solved in $$$O(m \cdot log{n})$$$ using a technique called "walking" on the segment tree. You start at the root and go left if there is a wanted value in the left subtree, otherwise you go right.

My submission: https://cses.fi/paste/fd5bc723278d272d9edfac/

List Removals can be solved in $$$O(n \cdot log{n})$$$ with the same technique.

My submission: https://cses.fi/paste/548144813e0f1a2a9ee375/

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you elaborate more on how walking can be used to solve List Removals. I was able to solve Hotel Queries, but I am confused on how it can be used for List Removals.

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Create a Segment Tree over an array of size n with all elements set to 1. 1 means that the element at that index hasn't been removed. Now for each query start walking on the segment tree until you find a prefix with sum $$$p_i$$$.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Is there anywhere I can learn about this technique and maybe practice some more problems related to this technique?

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You can check out the EDU section on segment trees. But this is not really something you practice problems on. I have only used it when cheesing a segment tree solution.

»
3 months ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

Bro it's 2024 now and dont use Mo A. to solve Range Distinct Value Queries any more.

You can solve it in $$$\mathcal O(n \log n)$$$ with a pretty short code.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please share your approach or the code without Mo Algorithm?

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 7   Vote: I like it 0 Vote: I do not like it

      Yes,You can solve Distinct Value Queries in O(nlogn) using a Binary Indexed Tree (BIT) or Segment Tree based on certain observations. I solved the problem using offline query on Binary Indexed Tree from left to right after sorting the query in increasing order.Before performing the query, add 1 to the index of the first occurrence of each value.I hope you will be able to understand the code.

      My Submission: Distinct Value Queries

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What are the topics I should learn first before solving those problems??

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    implementation

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can learn about segment trees here. It's fine if you don't understand advanced techniques such as lazy propagation on the first go. Just understand basic things first like range sums, point updates, etc.

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In Pizzeria Queries: I think answer should be min(left.query(1, i) + i, right.query(i, n) — i)

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Needed help with the Salary Queries problem. I am attaching my code.

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<bool> vb;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep1(i, n1, n2) for(int i = n1; i < n2; i++)
#define rep2(i, n1, n2) for(int i = n1; i > n2; i--)
#define Code_by_Kirtiman ios::sync_with_stdio(0); cin.tie(0);

const ll mod7 = 1000000007;
const ll mod9 = 998244353;
const ll INF = 1ll << 60;

template <typename T>
void takeArrayInput(vector<T> &a){
    for(int i = 0; i < a.size(); i++) cin >> a[i];
}

template <typename T>
void printArray(vector<T> &a){
    for(int i = 0; i < a.size(); i++) cout << a[i] << " ";
    cout << endl;
}

class segTree{
    public:
        ll size;
        vll sums;
 
        segTree(ll n){
            size = 1;
            while(size < n) size <<= 1;
            sums.assign(2*size, 0ll);
        }
 
        void build(vll &a, ll x, ll lx, ll rx){
            if(rx - lx == 1){
                if(lx < ll(a.size())){
                    sums[x] = a[lx];
                }
                return;
            }
            ll mid = lx + (rx - lx)/2;
            build(a, 2*x + 1, lx, mid);
            build(a, 2*x + 2, mid, rx);
            sums[x] = sums[2*x + 1] + sums[2*x + 2];
        }
 
        void build(vll &a){
            build(a, 0, 0, size);
        }
 
        void update(ll i, ll diff, ll x, ll lx, ll rx){
            if(rx - lx == 1){
                sums[x] += diff;
                return;
            }
            ll mid = lx + (rx - lx) / 2;
            if(i < mid){
                update(i, diff, 2*x + 1, lx, mid);
            }
            else{
                update(i, diff, 2*x + 2, mid, rx);
            }
            sums[x] = sums[2*x + 1] + sums[2*x + 2];
        }
 
        void update(ll i, ll diff){
            update(i, diff, 0, 0, size);
        }

        ll sum(ll l, ll r, ll x, ll lx, ll rx){
            if(lx >= r || rx <= l) return 0ll;
            if(lx >= l && rx <= r) return sums[x];
            ll mid = lx + (rx - lx) / 2;
            ll s1 = sum(l, r, 2*x + 1, lx, mid), s2 = sum(l, r, 2*x + 2, mid, rx);
            return s1 + s2;
        }
 
        ll sum(ll l, ll r){
            return sum(l, r, 0, 0, size);
        }
};

void solve(){
    ll n, q;
    cin >> n >> q;
    vll a(n);
    takeArrayInput(a);
    
    vector<pair<char, pair<ll, ll>>> queries(q);
    rep1(i, 0, q){
        cin >> queries[i].first >> queries[i].second.first >> queries[i].second.second;
    }

    set<ll> allNums;
    rep1(i, 0, n){
        allNums.insert(a[i]);
    }

    rep1(i, 0, q){
        if(queries[i].first == '?'){
            allNums.insert(queries[i].second.first);
        }
        allNums.insert(queries[i].second.second);
    }

    map<ll, ll> comp;
    ll curr = 0;
    auto it = allNums.begin();
    while(it != allNums.end()){
        comp[*it] = curr++;
        it++;
    }

    vll freq(curr, 0);
    rep1(i, 0, n){
        freq[comp[a[i]]]++;
    }

    segTree st(freq.size());
    st.build(freq);
    
    rep1(i, 0, q){
        if(queries[i].first == '!'){
            ll ind = queries[i].second.first, currVal = a[ind - 1], newVal = queries[i].second.second;
            a[ind - 1] = newVal;
            st.update(comp[currVal], -1);
            st.update(comp[newVal], 1);
        }
        else{
            ll l = queries[i].second.first, r = queries[i].second.second;
            cout << st.sum(comp[l], comp[r] + 1) << "\n";
        }
    }
}

signed main(){
    Code_by_Kirtiman

    int t = 1;
    // cin >> t;

    while(t--){
        solve();
    }

    return 0;
}

Why am I getting TLE?

Thanks in advance.