Pie-Lie-Die's blog

By Pie-Lie-Die, history, 4 years ago, In English

Recently I have been learning segment tree and so made a template for segment tree. I am not entirely sure that it is all correct and if it can be optimized further. Kindly go through it and if you find anything worth commenting like any mistakes or optimizations, please do so.

Here is the template:-


#include<bits/stdc++.h> using namespace std; class SegmentTree{ private : std::vector<int> st,A; vector<int> lazy; int n; public: SegmentTree(vector<int>& a) { A = a; n = a.size(); st.assign(4*n + 1, 0); // Max 4n nodes required lazy.assign(4*n+1, 0); // Max 4n nodes required build(1,0,n-1); // build segment tree } void print() // Print the st and lazy to debug { cout << "SegmentTree is as follows "<< endl; for(int c: st) { cout << c << " "; } cout << "\nLazy is as follows \n"; for(int c: lazy) { cout << c<< " "; } cout << endl; } void build(int i, int l, int r) // Method to build the segTree { if(l>r) return; if(l == r) { st[i] = A[l]; } else { build(2*i, l,(l+r)/2); build(2*i + 1, (l+r)/2 + 1, r); st[i] = st[2*i] + st[2*i + 1]; // Modify this as needed } } int rsq(int l, int r) // Range Sum query.Modify this // as needed for different problems. { l--; r--; return query(1,0,n-1,l,r); } void update_range(int l, int r, int diff) { l--,r--; update_lazy(1,0,n-1,l,r ,diff); } void update_lazy(int i, int a, int b, int l, int r, int diff) { if(lazy[i]!=0) { st[i] += (b-a+1)*diff; // Modify as needed if(a!=b) // propagate if not leaf { lazy[2*i] = lazy[i]; lazy[2*i+1] = lazy[i]; } lazy[i] = 0; } if(l>r || l>b || r<a) // Out of range return; if(a>=l && r<=b) // Completely in range { st[i] = (b-a+1)*diff; if(a!=b) // If not leaf then propagate { lazy[2*i] += diff; lazy[2*i+1] += diff; } return; } update_lazy(2*i, a, (a+b)/2, l, r, diff); update_lazy(2*i+1, (a+b)/2+1, b, l, r, diff); st[i] = st[2*i] + st[2*i+1]; // Modify as needed } int query(int i, int a,int b, int l, int r) { if(lazy[i]!=0) { st[i] += (b-a+1)*lazy[i]; if(a!=b) { lazy[2*i] = lazy[i]; lazy[2*i+1] = lazy[i]; } lazy[i] = 0; } if(r<a || b<l || a > b) return 0; if(l<=a && r>=b) return st[i]; return query(2*i, a,(a+b)/2, l,r) + query(2*i+1,(a+b)/2 + 1, b,l,r); // MOdify } }; int main() { vector<int> a(8); for(int i=0; i<8; i++) a[i] = i+1; SegmentTree* sst = new SegmentTree(a); cout << sst->rsq(1,4) << endl; sst->update_range(1,4,2); cout << sst->rsq(1,4); return 0; }

Thanks in advance!

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

| Write comment?
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

You can test it locally for n <= 1000, against a brute force, to be sure that it works correctly. Something like this I did for my implementation of segment tree :

Basically generate random array, then performs 900 commands, some are queries, some are updates

Generate random indices x, y such that x <= y Add random number to all a[x],a[x+1],...,a[y] for the update command Check sum a[x]+...+a[y] for query command.


fr(_, 100) { int n=randInt(0, 500)+100; fr(i, n)a[i]=randInt(1, 500); t.init(a, n); fr(__, 900) { int cmd=randInt(1, 2); if(cmd==1) { // query int x=randInt(0, n-1);int y=randInt(0, n-x-1)+x; int sm=0;frr(i, x, y)sm+=a[i];int sm2=t.query(x, y, 0, n-1, 0); assert(sm==sm2); }else { // update int x=randInt(0, n-1);int y=randInt(0, n-x-1)+x, z=randInt(1, 3); frr(i, x, y)a[i]+=z; t.update(x, y, z, 0, n-1, 0); } } }

fr -> for loop,

randInt(a,b) -> function that i wrote that returns random integer >= a and <= b

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

There is probably code online that implements segment tree, so you can probably look at that and compare. Also test like others have mentioned. However, in my opinion, segment trees are not needed if you are below 1900 (this goes for me too). Since you don’t have many contests, I’m not sure your actual rating, but maybe try focusing on algorithms closer to your skill level and you’ll get better faster.

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

    Thanks, Pranay!. I didn't know that below 1900 problems don't need segment trees. Regarding my ratings, I think I belong to the around 1400 range. But that don't matter as long as I am improving because the learning curve is pretty steep. Do you mind if I ask you for help if I get stuck in 1400-1500 problems? Thank you and best Wishes!

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

      If you want to improve your rating past 1400-1500, there’s not much more than practice different types of problems in that range. I find myself asking the same question for Div 2 D problems to get to 1900-2100, but when trying to answer this same question for 1400-1500, I don’t have any solid advice. Try participating in more contests and you’ll notice patterns. Sample cases and your own cases also help. Usually it is some bizarre question that sounds complicated but in reality boils down to 2-3 cases. You can find some other posts that have more in depth guides made by more experienced users.

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

    I think I used segment trees in div2B-level tasks several times because some solution using segment tree was immediately obvious while the smart solution wasn't.

    So I think it is useful to have those seemingly overkill data structures in your arsenal even if you are green or gray or whatever (besides, when you learn them, you understand general theory better, which is just as important as problemsolving).

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

      Any examples? I have not yet so that’s interesting. I feel like there will be some gap that forms in understanding if you aren’t able to find the “easier” solution, and it may take more time too

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 4   Vote: I like it +1 Vote: I do not like it

        75381067

        When I was writing the contest, I understood literally nothing about the problem. All I understood was that (array is a permutation <=> min and max of frequency array on segment [1, max] are 1), I coded that bruteforce solution which was now fast enough thanks to segment tree and got an accepted.

        73099363

        Another example where overcomplicated solution is immediately obvious (at least it was to me, I wrote some stuff on a piece of paper and immediately got an idea for a query-sorting+segment tree+compressing stuff solution), yet intended solution is like 10 lines of code with 2 pointers after sorting.

        I'm not saying it is a good thing, I'm just saying that you never know what solution pops up in your head and that knowing stuff is better than not knowing it.

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

          Hmm interesting. I don’t fully understand how your segment tree for this problem works 100% but that’s cool way to think about the problem. I mean yeah it doesn’t hurt to learn/implement segment trees but I feel that time could be spent learning more appropriate algorithms at the range and in the long run will help more. But yeah doesn’t hurt

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can verify segment tree on cses or on russian version of CF in EDU tab there are good problems about basic segment trees.

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

Hey bro, Are you now sure about this temp? . And I will use it if you allow me..

»
20 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Useless blog