From CP Algorithms

void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = 0;
    }
}

void update(int v, int tl, int tr, int l, int r, int add) {
    if (l > r)
        return;
    if (l == tl && r == tr) {
        t[v] += add;
    } else {
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), add);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, add);
    }
}

int get(int v, int tl, int tr, int pos) {
    if (tl == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        return t[v] + get(v*2, tl, tm, pos);
    else
        return t[v] + get(v*2+1, tm+1, tr, pos);
}

For this problem, I used a lazy segment tree with a slight twist. Instead of a standard push function to propagate updates, I handle the accumulation during the query itself.

For updates (type 1): The process is standard. I traverse the tree and add the update value to the lazy tag of any node whose range is fully contained within the query range.

For queries (type 2): To find the value at a position pos, I traverse from the root down to the leaf for pos. Along this path, I accumulate the sum of lazy values from every node visited. The final answer is the leaf's initial value plus this accumulated sum.

void push(int t_idx, int tl, int tr) {
    if (lazy[t_idx] == 0) return;

    int mid = tl + ((tr - tl) / 2);
    tree[2*t_idx] += (mid - tl + 1) * lazy[t_idx];
    lazy[2*t_idx] += lazy[t_idx];

    tree[2*t_idx+1] += (tr - (mid + 1) + 1) * lazy[t_idx];
    lazy[2*t_idx+1] += lazy[t_idx];

    lazy[t_idx] = 0;
}

void apply(int t_idx, int tl, int tr, int val) {
    tree[t_idx] += (tr - tl + 1) * val;
    lazy[t_idx] += val;
}

void merge(int t_idx) { tree[t_idx] = tree[2*t_idx] + tree[2*t_idx + 1]; }

void build_tree(int t_idx, int l, int r) {
    if (l == r) {
        tree[t_idx] = vec[l];
        return;
    }
    int mid = l + ((r - l) / 2);
    build_tree(2*t_idx, l, mid);
    build_tree(2*t_idx + 1, mid + 1, r);
    merge(t_idx);
}

void update(int t_idx, int tl, int tr, int l, int r, int val) {
    if (tl > r || tr < l) return;

    if (l <= tl && r >= tr) {
        apply(t_idx, tl, tr, val);
        return;
    }

    push(t_idx, tl, tr);
    int mid = tl + ((tr - tl) / 2);
    update(2*t_idx, tl, mid, l, r, val);
    update(2*t_idx + 1, mid + 1, tr, l, r, val);
    merge(t_idx);
}

int query(int t_idx, int tl, int tr, int l, int r) {
    if (tl > r || tr < l) return 0;
    if (l <= tl && r >= tr) return tree[t_idx];

    push(t_idx, tl, tr);
    int mid = tl + ((tr - tl) / 2);
    return query(2*t_idx, tl, mid, l, r) + query(2*t_idx + 1, mid + 1, tr, l, r);
}

My approach avoids a separate push() function by redefining how updates and queries work. The core idea is to keep parent nodes updated eagerly while leaving lazy tags for their children to be resolved at query time.

For updates (Query-1):

For a range update on [l, r] with value val, I traverse the tree. If a node's range [tl, tr] is fully contained within [l, r], I apply the update directly to it:

• tree[node] += (tr - tl + 1) * val
• lazy[node] += val

When returning after recursive calls, I merge the results from its children:

• tree[parent] = tree[left_child] + tree[right_child]

This ensures that all ancestors of the updated nodes immediately reflect the new total sum.

For queries (Query-2):

For a range query on [l, r], I traverse the tree, keeping track of an accumulated_lazy sum from the ancestors. During the traversal from a parent to a child, I update the sum: accumulated_lazy += parent.lazy. If a node's range [tl, tr] is fully contained within the query range [l, r], it contributes to the final answer. Its correct sum is its stored tree value plus the pending updates from all its ancestors that we've accumulated. The value to return is:

tree[node] + (tr - tl + 1) * accumulated_lazy

If a node's range only partially overlaps, I recurse on its children, passing down the updated accumulated_lazy value.

This works because the lazy tag on a node signifies an update that has been applied to its own tree value but has not yet been propagated to its children. Our query manually carries this information down the path.

From CP Algorithms

void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = max(t[v*2], t[v*2 + 1]);
    }
}

void push(int v) {
    t[v*2] += lazy[v];
    lazy[v*2] += lazy[v];
    t[v*2+1] += lazy[v];
    lazy[v*2+1] += lazy[v];
    lazy[v] = 0;
}

void update(int v, int tl, int tr, int l, int r, int addend) {
    if (l > r) 
        return;
    if (l == tl && tr == r) {
        t[v] += addend;
        lazy[v] += addend;
    } else {
        push(v);
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), addend);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, addend);
        t[v] = max(t[v*2], t[v*2+1]);
    }
}

int query(int v, int tl, int tr, int l, int r) {
    if (l > r)
        return -INF;
    if (l == tl && tr == r)
        return t[v];
    push(v);
    int tm = (tl + tr) / 2;
    return max(query(v*2, tl, tm, l, min(r, tm)), 
               query(v*2+1, tm+1, tr, max(l, tm+1), r));
}

For updates (Query-1):

First, I go down the tree. When I find a node that is completely inside the update range, I change its values. The logic is simple: if I add val to all numbers in a range, the biggest number in that range also just increases by val. So, I do this:

• tree[node] += val; lazy[node] += val;

Then, when the code goes back up the tree after recursive calls, I fix the parent's value. The parent's new maximum is just the max of its two children.

• tree[parent] = max(tree[left_child], tree[right_child]);

This makes sure that all the nodes above are also correct.

For queries (Query-2):

To find the max, I go down the tree. I keep track of the lazy values from the parents in a variable called accumulated_val.

• accumulated_val += lazy[node]

If a node is completely inside the query range, I have the answer for it. The real maximum is the value stored in the node, plus the accumulated_val I brought down from its parents.

• return tree[node] + accumulated_val

If a node is partly in the range, I can't use its value. I have to ask its left and right children for their respective maximums and then return the bigger of the two.

If a node is outside the range, I just return a very small number.

From CP Algorithms

void push(int v) {
    if (marked[v]) {
        t[v*2] = t[v*2+1] = t[v];
        marked[v*2] = marked[v*2+1] = true;
        marked[v] = false;
    }
}

void update(int v, int tl, int tr, int l, int r, int new_val) {
    if (l > r) 
        return;
    if (l == tl && tr == r) {
        t[v] = new_val;
        marked[v] = true;
    } else {
        push(v);
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), new_val);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, new_val);
    }
}

int get(int v, int tl, int tr, int pos) {
    if (tl == tr) {
        return t[v];
    }
    push(v);
    int tm = (tl + tr) / 2;
    if (pos <= tm) 
        return get(v*2, tl, tm, pos);
    else
        return get(v*2+1, tm+1, tr, pos);
}

For updates (Query-1):

First, I go down the tree. Each node stores a pair: {value, timestamp}. The timestamp is just the query number. When I find a node that is completely inside the update range, I update its stored pair. The logic is simple: this new assignment overwrites any older ones for this entire block. So, I do this:

• tree[node] = {val, k};

I return from this node, not going further down.

For queries (Query-2):

To find the value, I go down the single path from the root to the leaf for position pos. I keep track of the pair with the latest timestamp I've seen so far in a variable called latest_update. And then I return the value of latest update.