Range Update Queries

Given an array of n integers, your task is to process q queries of the following types:

1. increase each value in the range [a,b] by u.

2. what is the value at position k?

Example:

Input: n = 8, q = 3, a = {3, 2, 4, 5, 1, 1, 5, 3}, queries = {{2, 4}, {1, 2, 5, 1}, {2, 4}}

Output:

5
6

Approach:

C++

#include <bits/stdc++.h>
using namespace std;
long long int tree[4000011];
long long int arr[1000001];
long long int lazy[4000011];
void build(long long int node, long long int start,
           long long int end)
{
    if (start == end)
    {
        tree[node] = arr[start];
        return;
    }
    long long int mid = (start + end) / 2;
    build(2 * node, start, mid);
    build(2 * node + 1, mid + 1, end);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}
void update(long long int node, long long int start,
            long long int end, long long int l,
            long long int r, long long int val)
{
    if (lazy[node] != 0)
    {
        long long int dx = lazy[node];
        lazy[node] = 0;
        tree[node] += dx * (end - start + 1);
        if (start != end)
        {
            lazy[2 * node] += dx;
            lazy[2 * node + 1] += dx;
        }
    }
    if (start > end || start > r || end < l)
        return;
    if (start >= l && end <= r)
    {
        long long int dx = (end - start + 1) * val;
        tree[node] += dx;
        if (start != end)
        {
            lazy[2 * node] += val;
            lazy[2 * node + 1] += val;
        }
        return;
    }
    long long int mid = (start + end) / 2;
    update(2 * node, start, mid, l, r, val);
    update(2 * node + 1, mid + 1, end, l, r, val);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}
long long int query(long long int node,
                    long long int start,
                    long long int end, long long int l,
                    long long int r)
{
    if (lazy[node] != 0)
    {
        long long int dx = lazy[node];
        lazy[node] = 0;
        tree[node] += dx * (end - start + 1);
        if (start != end)
        {
            lazy[2 * node] += dx;
            lazy[2 * node + 1] += dx;
        }
    }
    if (start > end || r < start || l > end)
        return 0;
    if (start >= l && r >= end)
        return tree[node];
    long long int mid = (start + end) / 2;
    long long int p1 = query(2 * node, start, mid, l, r);
    long long int p2 = query(2 * node + 1, mid + 1, end, l, r);
    return p1 + p2;
}
int main()
{

    long long int n = 8, q = 3;
    vector<long long int> a = {3, 2, 4, 5, 1, 1, 5, 3};

    vector<vector<long long int>> queries = {{2, 4},
                                             {1, 2, 5, 1},
                                             {2, 4}};
    for (long long int i = 1; i <= n; i++)
        arr[i] = a[i - 1];
    build(1, 1, n);

    for (long long int i = 0; i < q; i++)
    {
        long long int x = queries[i][0];

        if (x == 1)
        {
            long long int l = queries[i][1];
            long long int r = queries[i][2];
            long long int u = queries[i][3];

            update(1, 1, n, l, r, u);
        }
        else
        {
            long long int l = queries[i][1];

            cout << query(1, 1, n, l, l) << "\n";
        }
    }
    return 0;
}