Segment tree - help

I have learnt the implementation of a basic Segment tree that can perform two operations:

  • Point Update - Updates specific node and its ancestors recursively
  • Range Query - Returns the result of a function over the range

I wanted to test my code, so I searched for problems under Segment Trees, found this problem. Unlike the first few problems in CSES, this problem requires range update (instead of point update). I am totally stuck.

What I actually need help with:

  • How to handle range updates efficiently?
  • Should I learn any other algorithm to solve this problem?

Can anyone help me with this?
Thanks in advance

@cubefreak777

I think for range update Lazy propagation is used.

1 Like

Learn about lazy propagation first and then learn how to manipulate a segment tree to work for any general type of query & updates.

General purpose segtree implementation(I'm not the author of this code)
//credits : WILLIAM LIN
template<class T, class U> void vti(vector<T> &v, U x, size_t n) {
  v=vector<T>(n, x);
}
template<class T, class U> void vti(vector<T> &v, U x, size_t n, size_t m...) {
  v=vector<T>(n);
  for(auto &a:v)
    vti(a, x, m);
}
struct {
  struct d1 {
    int len=1;
    long long sum;
    long long mn;
    long long mx;
  };
  struct d2 {
    bool res=0;
    long long add=0;
  };
  d1 d1d1(d1 a, d1 b) {
    d1 c;
    c.len=a.len+b.len;
    c.sum=a.sum+b.sum;
    c.mn=min(a.mn, b.mn);
    c.mx=max(a.mx, b.mx);
    return c;
  }
  void d1d2(d1& a, d2& b) {
    if(b.res) {
      a.sum=0;
      a.mn=0;
      a.mx=0;
    }
    a.sum+=a.len*b.add;
    a.mn+=b.add;
    a.mx+=b.add;
  }
  void d2d2(d2& a, d2& b) {
    if(b.res) {
      a.res=1;
      a.add=0;
    }
    a.add+=b.add;
  }
  template<class T> d1 cd1(T& x) {
    d1 a;
    a.sum=x;
    a.mn=x;
    a.mx=x;
    return a;
  }
  int n;
  vector<d1> st;
  vector<d2> lz;
  template<class T> void bld(vector<T>& a, int i, int l2, int r2) {
    if(l2==r2) {
      st[i]=cd1(a[l2]);
      return;
    }
    int m2=(l2+r2)/2;
    bld(a, 2*i, l2, m2);
    bld(a, 2*i+1, m2+1, r2);
    st[i]=d1d1(st[2*i], st[2*i+1]);
  }
  template<class T> void bld(vector<T> a) {
    n=sz(a);
    vti(st, d1{}, 4*n);
    vti(lz, d2{}, 4*n);
    bld(a, 1, 0, n-1);
  }
  void app(int i, d2 &x) {
    d1d2(st[i], x);
    d2d2(lz[i], x);
  }
  void psh(int i) {
    app(2*i, lz[i]);
    app(2*i+1, lz[i]);
    lz[i]={};
  }
  template<class T> void set(int l1, T& x, int i, int l2, int r2) {
    if(l2==r2) {
      st[i]=cd1(x);
      return;
    }
    int m2=(l2+r2)/2;
    psh(i);
    if(l1<=m2)
      set(l1, x, 2*i, l2, m2);
    else
      set(l1, x, 2*i+1, m2+1, r2);
    st[i]=d1d1(st[2*i], st[2*i+1]);
  }
  template<class T> void set(int l1, T x) {
    set(l1, x, 1, 0, n-1);
  }
  void upd(int l1, int r1, d2& x, int i, int l2, int r2) {
    if(l1<=l2&&r2<=r1) {
      app(i, x);
      return;
    }
    int m2=(l2+r2)/2;
    psh(i);
    if(l1<=m2)
      upd(l1, r1, x, 2*i, l2, m2);
    if(m2<r1)
      upd(l1, r1, x, 2*i+1, m2+1, r2);
    st[i]=d1d1(st[2*i], st[2*i+1]);
  }
  void upd(int l1, int r1, d2 x) {
    upd(l1, r1, x, 1, 0, n-1);
  }
  d1 qry(int l1, int r1, int i, int l2, int r2) {
    if(l1<=l2&&r2<=r1)
      return st[i];
    int m2=(l2+r2)/2;
    psh(i);
    if(l1>m2)
      return qry(l1, r1, 2*i+1, m2+1, r2);
    if(r1<=m2)
      return qry(l1, r1, 2*i, l2, m2);
    return d1d1(qry(l1, r1, 2*i, l2, m2), qry(l1, r1, 2*i+1, m2+1, r2));
  }
  d1 qry(int l1, int r1) {
    return qry(l1, r1, 1, 0, n-1);
  }
} st;
1 Like

@suman_18733097 , I used this problem to test my point update - range query segment tree code.
https://www.codechef.com/problems/AVNP5

and to do range updates and point queries we need to just change the previous segment tree update and query function.
for reference use this :- Segment Tree - Competitive Programming Algorithms

1 Like

Thank you, everyone. I will go through each of them in a while.

2 Likes

You can check out https://www.codeintuition.io/blog/niBFVvULgdGGRQwSa6SLJ to get a very good basic understanding of segment trees.

you can write a brute force solution to array and check corresponding answer returned by
segment tree. do this for big arrays of lengths approx 1000 and try to put duplicate values.