[Template] Segment Tree Lazy Propagation

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Algorithm         : Segment Tree Lazy Propagation
Source            : 
Category          : 
Algorithm         : 
Verdict           : Tested

struct data
{
      ll sum;
      data() : sum(0) {}
};
 
ll store[Max];
 
struct SegTree
{
      int N;
      vector <data> st;
      vector <bool> cLazy;
      vector <ll> lazy;
 
      void init(int n)
      {
            N = n;
            st.resize(4 * N + 5);
            cLazy.resize(4 * N + 5);
            lazy.resize(4 * N + 5);
      }
      void merge(data &cur, data &l, data &r)
      {
            cur.sum = (l.sum + r.sum) % mod;
      }
      void propagate(int node, int L, int R)
      {
            if (L != R)
            {
                  int lft = node * 2;
                  int rgt = lft + 1;
                  cLazy[lft] = 1;
                  cLazy[rgt] = 1;
                  lazy[lft] = (lazy[lft] + lazy[node]) % mod;
                  lazy[rgt] = (lazy[rgt] + lazy[node]) % mod;
            }
            st[node].sum = (st[node].sum + lazy[node]) % mod;
            cLazy[node] = 0;
            lazy[node] = 0;
      }
      void build(int node, int L, int R)
      {
            if (L == R)
            {
                  st[node].sum = store[L];
                  cLazy[node] = 0;
                  lazy[node] = 0;
                  return;
            }
            int lft = node * 2;
            int rgt = lft + 1;
            int M = (L + R) / 2;
            build(lft, L, M);
            build(rgt, M + 1, R);
            merge(st[node], st[lft], st[rgt]);
      }
      data Query(int node, int L, int R, int i, int j)
      {
            if (cLazy[node]) propagate(node, L, R);
            if (j < L || i > R) return data();
            if (i <= L && R <= j) return st[node];
            int lft = node * 2;
            int rgt = lft + 1;
            int M = (L + R) / 2;
            data p = Query(lft, L, M, i, j);
            data q = Query(rgt, M + 1, R, i, j);
            data cur;
            merge(cur, p, q);
            return cur;
      }
      data pQuery(int node, int L, int R, int pos)
      {
            if (cLazy[node]) propagate(node, L, R);
            if (L == R) return st[node];
            int lft = node * 2;
            int rgt = lft + 1;
            int M = (L + R) / 2;
            if (pos <= M) return pQuery(lft, L, M, pos);
            else return pQuery(rgt, M + 1, R, pos);
      }
      void update(int node, int L, int R, int i, int j, ll val)
      {
            if (cLazy[node]) propagate(node, L, R);
            if (j < L || i > R) return;
            if (i <= L && R <= j)
            {
                  cLazy[node] = 1;
                  lazy[node] = (lazy[node] + val) % mod;
                  propagate(node, L, R);
                  return;
            }
            int lft = node * 2;
            int rgt = lft + 1;
            int M = (L + R) / 2;
            update(lft, L, M, i, j, val);
            update(rgt, M+1, R, i, j, val);
            merge(st[node], st[lft], st[rgt]);
      }
      void pUpdate(int node, int L, int R, int pos, ll val)
      {
            if (cLazy[node]) propagate(node, L, R);
            if (L == R)
            {
                  cLazy[node] = 1;
                  lazy[node] = (lazy[node] + val) % mod;
                  propagate(node, L, R);
                  return;
            }
            int lft = node * 2;
            int rgt = lft + 1;
            int M = (L + R) / 2;
            if (pos <= M) pUpdate(lft, L, M, pos, val);
            else pUpdate(rgt, M+1, R, pos, val);
            merge(st[node], st[lft], st[rgt]);
      }
      data query(int pos)
      {
            return pQuery(1, 1, N, pos);
      }
      data query(int l, int r)
      {
            return Query(1, 1, N, l, r);
      }
      void update(int pos, ll val)
      {
            pUpdate(1, 1, N, pos, val);
      }
      void update(int l, int r, ll val)
      {
            update(1, 1, N, l, r, val);
      }
};