Range minimum query and update for intervals

Question

I need a range minimum query data structure that supports three operations:
 - initialize with array A[n]
 - update(i,j,v) - add v to all elements from the range A[i]...A[j]
 - query (i,j) - find the minimal element from the range A[i]...A[j]

Both update and query must run in O(log n) time and the structure must take O(n) space.

Answer 1

Thanks for the help!
I managed to do this with the Lazy Propagation technique.

The initialization is with a vector instead of an array.
It is easy to be turned into a maximum query structure... replace all the min-s with max-s and the number 2100000000 with -2100000000

#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

class IntervalTree
{
    int* tree;
    int* lazy;
    int n;

    void build_tree(const vector<int>& v, int node, int a, int b)
    {
        if (a > b) return;

        if (a == b) { tree[node] = v[a]; return; }

        build_tree(v, node * 2, a, (a + b) / 2);
        build_tree(v, node * 2 + 1, 1 + (a + b) / 2, b);
        tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
    }

    void update_lazy(int node, int a, int b)
    {
        tree[node] += lazy[node];

        if (a != b) 
        { 
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }

        lazy[node] = 0;
    }

    void update_tree(int node, int a, int b, int i, int j, int value)
    {
        if (lazy[node] != 0) update_lazy(node,a,b);

        if (a > b || a > j || b < i) return;

        if (a >= i && b <= j) 
        {
            tree[node] += value;
            if (a != b) 
            {
                lazy[node * 2] += value;
                lazy[node * 2 + 1] += value;
            }
            return;
        }

        update_tree(node * 2, a, (a + b) / 2, i, j, value);
        update_tree(1 + node * 2, 1 + (a + b) / 2, b, i, j, value);

        tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
    }

    int query_tree(int node, int a, int b, int i, int j)
    {
        if (a > b || a > j || b < i) return 2100000000;

        if (lazy[node] != 0) update_lazy(node,a,b);

        if (a >= i && b <= j) return tree[node];

        int q1 = query_tree(node * 2, a, (a + b) / 2, i, j);
        int q2 = query_tree(1 + node * 2, 1 + (a + b) / 2, b, i, j);

        return min(q1, q2);
    }

public:
    IntervalTree(const vector<int>& v)
    {
        n = v.size();

        int s = 2*pow(2, ceil(log2(v.size())));

        tree = new int[s];

        lazy = new int[s];

        memset(lazy, 0, sizeof lazy);

        build_tree(v, 1, 0, n - 1);
    }

    void update(int idx1, int idx2, int add)
    {
        update_tree(1, 0, n - 1, idx1, idx2, add);
    }

    int query(int idx1, int idx2)
    {
        return query_tree(1, 0, n - 1, idx1, idx2);
    }
};