Segment Tree

/*
 Created by Saidolda Bayan.
 Copyright (c) 2015 Bayan. All rights reserved.
 LANG: C++
 */
#include <bits/stdc++.h>

#define _USE_MATH_DEFINES
#define y1 lalka
#define right napravo
#define left nalevo
#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;
using pii = pair<int, int>;
using ll = long long;

const int INF = (int)1e9+7, mod = (int)1e9+9, pw = 31, N = (int)1e5+123, M = (int)1e6+123;
const double eps = 1e-11;
const long long inf = 1e18;

struct node{
    ll sum, add;
    int l, r;
}t[4 * N];

int a[N], n;

void push(int v){
    if(t[v].add){
        t[v].sum += 1ll * (t[v].r - t[v].l + 1) * t[v].add;
        if(t[v].l < t[v].r){
            t[v+v].add += t[v].add;
            t[v+v+1].add += t[v].add;
        }
        t[v].add = 0;
    }
}
void build(int v = 1, int tl = 1, int tr = n){
    t[v].l = tl;
    t[v].r = tr;
    if(tl == tr){
        t[v].sum = a[tl];
    }
    else{
        int mid = (tl + tr) / 2;
        build(v+v, tl, mid);
        build(v+v+1, mid+1, tr);
        t[v].sum = t[v+v].sum + t[v+v+1].sum;
    }
}

ll get(int l, int r, int v = 1, int tl = 1, int tr = n){
    push(v);
    if(max(l, tl) > min(r, tr)) return 0;
    if(l <= tl && tr <= r) return t[v].sum;
    int mid = (tl + tr) / 2;
    return get(l, r, v+v, tl, mid) + get(l, r, v+v+1, mid+1, tr);
}

void upd(int l, int r, ll x, int v = 1, int tl = 1, int tr = n){
    push(v);
    if(max(l, tl) > min(r, tr)) return;
    if(l <= tl && tr <= r){
        t[v].add += x;
        push(v);
        return;
    }
    int mid = (tl + tr) / 2;
    upd(l, r, x, v+v, tl, mid);
    upd(l, r, x, v+v+1, mid+1, tr);
    t[v].sum = t[v+v].sum + t[v+v+1].sum;
}
int main ()
{
    ios_base::sync_with_stdio(0);cin.tie(NULL);
#ifndef DEBUG
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
#endif



    return 0;
}