[toph.co] Just Another Range Query

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Just Another Range Query
Source            : toph.co
Category          : Data Structure
Algorithm         : Implicit Segment Tree, Lazy Propagation
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll              long long
 
struct node
{
      ll sum, lazy;
      node *lft, *rgt;
      node() : sum(0), lazy(0), lft(nullptr), rgt(nullptr) {}
 
      ~node()
      {
            delete lft;
            delete rgt;
      }
};
 
typedef node*       pnode;
 
inline void updateLazy(pnode root, ll a, ll b, ll val)
{
      root->sum += (b - a + 1) * val;
      root->lazy += val;
}
 
inline void updateNode(pnode root, ll a, ll b)
{
      ll mid = (a + b) >> 1;
      if (root->lft == nullptr) root->lft = new node();
      root->lft->lazy += root->lazy;
      root->lft->sum += (mid - a + 1) * root->lazy;
 
      if (root->rgt == nullptr) root->rgt = new node();
      root->rgt->lazy += root->lazy;
      root->rgt->sum += (b - mid) * root->lazy;
 
      root->lazy = 0;
}
 
inline void update(pnode root, ll a, ll b, ll i, ll j, ll val)
{
      if (a == i && b == j)
      {
            updateLazy(root, a, b, val);
            return;
      }
      if (root->lazy != 0)
      {
            updateNode(root, a, b);
      }
      ll mid = (a + b) >> 1;
      if (root->lft == nullptr) root->lft = new node();
      if (root->rgt == nullptr) root->rgt = new node();
      if (j <= mid)
      {
            update(root->lft, a, mid, i, j, val);
      }
      else if (i > mid)
      {
            update(root->rgt, mid+1, b, i, j, val);
      }
      else
      {
            update(root->lft, a, mid, i, mid, val);
            update(root->rgt, mid+1, b, mid+1, j, val);
      }
      root->sum = root->lft->sum + root->rgt->sum;
}
 
inline ll query(pnode root, ll a, ll b, ll i, ll j)
{
      if (a == i && b == j) return root->sum;
      if (root->lazy != 0)
      {
            updateNode(root, a, b);
      }
      ll mid = (a + b) >> 1;
      ll res = 0;
      if (root->lft == nullptr) root->lft = new node();
      if (root->rgt == nullptr) root->rgt = new node();
      if (j <= mid)
      {
            res += query(root->lft, a, mid, i, j);
      }
      else if (i > mid)
      {
            res += query(root->rgt, mid+1, b, i, j);
      }
      else
      {
            res += query(root->lft, a, mid, i, mid);
            res += query(root->rgt, mid+1, b, mid+1, j);
      }
      return res;
}
 
inline ll getSum(ll l, ll r)
{
      --l;
      ll suml = (1LL * l * (l+1)) / 2;
      ll sumr = (1LL * r * (r+1)) / 2;
      return sumr - suml;
}
 
inline void clean(pnode root)
{
      if (root == nullptr) return;
      clean(root->lft);
      clean(root->rgt);
      delete root;
}
 
 
int main()
{
      //freopen("in.txt", "r", stdin);
 
      ios_base::sync_with_stdio(false);
      cin.tie(nullptr);
 
      pnode root = new node();
      ll n, q;
      cin >> n >> q;
      while (q--)
      {
            ll type;
            cin >> type;
            if (type == 1)
            {
                  ll l, r;
                  ll val;
                  cin >> l >> r >> val;
                  if (l > r) swap(l, r);
                  update(root, 1, n, l, r, val);
            }
            else
            {
                  ll l, r;
                  cin >> l >> r;
                  if (l > r) swap(l, r);
                  ll tsum = getSum(l, r) - query(root, 1, n, l, r);
                  cout << tsum << endl;
            }
      }
}