nskybytskyi's blog

Range Queries and Segment Tree Training
By nskybytskyi, 4 years ago, In English

It's been a while, but we are back with another Codeforces Gym!

Translated statements and my solutions are here, and statements are also added to the gym itself.

Today I will talk about various problems involving range queries in general, and segment trees in particular.

First, I describe simple problems with range queries, such as sum/min/max on a segment without any updates. It is essential to understand that sometimes you don't need any advanced data structures to process range queries. In some problems, you can write a for loop, use prefix sums, or precompute a sparse table. However, when update queries come into play, the need for better data structures arise, and here segment tree, and lazy segment tree come into play. Their applications can seem practically unlimited, but at the very end, we realize that there are some limitations. Because of that, we introduce our final data structure, which supports Split and Merge operations.

Watch the theory here, or skip straight to the practice session if you already know the theory.

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

Comments Comments (11)
| Write comment?
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Thank you nskybytskyi.

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Starting in 15 minutes!

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

really excited!!!

thank you for putting in the effort to do such an amazing thing.

→ Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Can we please have more practice problems on segtrees? These are somewhat standard, lecture-style.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    I somewhat agree with you. The problems from this gym are designed to introduce people to the topic of range queries. If you already solved them you are welcome to the sequel gyms: first and second. Unfortunately, I haven't translated them just yet, so you will need the help of the google translate or something, and potentially https://2cyr.com/decode/?lang=en to fix the encoding. I will add English statements to the gyms once I translate the problems.

    → Reply
»
4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Hey guys, I have encountered a problem in cases problem Dynamic Sum Queries. My code fails for the second test case

Your code here...
#include <bits/stdc++.h>
using namespace std;

int n,q;
vector<long long> a(200005,0);
vector<long long> feenwick_tree(200005,0);

long long sum(int k){
    long long s=0;
    while(k>=1){
        s += feenwick_tree[k];
        k -= k&-k;
    }
    return s;
}

void add(int k, long long x){
    while(k<=n){
        feenwick_tree[k] += x;
        k += k&-k;
    }
}

int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++){
        add(i,a[i]);
    }
    while(q-->0){
        long long q,i,j;
        cin>>q>>i>>j;
        if(q==1){
            j = j-a[i];
            add(i,j);
        }
        else{
            long long x1 = sum(j);
            long long x2 = sum(i-1);
            if(i==1)
                cout<<x1<<"\n";
            else
                cout<<x1-x2<<"\n";
        }
    }
    return 0;
}

Thank you, in advance.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please at least post the link to the problem so that people can test their solutions?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      Your text to link here...

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Your solution fails the following testcase:

        1 3
1
1 1 2
1 1 2
2 1 1

        Your output is 3 and the expected answer is 2.

        It happens because you always add j - a[i] regardless of whether the value of a[i] has changed or not. Update the value of a[i] (a[i]+=j;) after the query to your Fenwick Tree and you should be fine.

        → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Hey nskybytskyi can you please make a contest mashup or question list from easy to hard so that we can try and maybe later you can make a editorial video!

→ Reply