Consider an array of (n) integers (a_1, a_2, \cdots, a_n). Two types of operations are supported:

1. Add a value (d) to all elements from index (l) to (r).
2. Query the maximum element within the range ([l, r]).

To efficiently handle these operations, we use a segment tree enhanced with lazy propagation. This technique introduces a lazy tag to defer updates until necessary.

The core idea behind lazy tags is to delay the application of updates. When traversing down the tree during a query or modification, pending updates (tags) are propagated to child nodes—a process known as pushdown. Applying a new tag to child nodes is referred to as applytag.

Steps for pushdown operation:

1. Execute only when there's an active tag. This avoids unnecessary computations.
2. Transfer current node’s tag to its left and right children.
3. Clear or reset the current node's tag.

Steps for applytag operation:

1. Combine the existing tag with the new one.
2. Update the node's data using the combined tag.

Implementation begins by defining structures for data (Info) and updates (Tag). The combination logic for both is encapsulated in overloaded operators.

struct Data {
    long long maxValue;
};

struct Update {
    long long delta;
};

struct TreeNode {
    Data info;
    Update lazy;
} tree[4 * N];

Data operator+(const Data& lhs, const Data& rhs) {
    Data result;
    result.maxValue = std::max(lhs.maxValue, rhs.maxValue);
    return result;
}

Data operator+(const Data& data, const Update& upd) {
    Data result;
    result.maxValue = data.maxValue + upd.delta;
    return result;
}

Update operator+(const Update& u1, const Update& u2) {
    Update result;
    result.delta = u1.delta + u2.delta;
    return result;
}

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

void applyTag(int nodeId, Update tag) {
    tree[nodeId].info = tree[nodeId].info + tag;
    tree[nodeId].lazy = tree[nodeId].lazy + tag;
}

void propagate(int nodeId) {
    if (tree[nodeId].lazy.delta != 0) {
        applyTag(nodeId * 2, tree[nodeId].lazy);
        applyTag(nodeId * 2 + 1, tree[nodeId].lazy);
        tree[nodeId].lazy = {0};
    }
}

Main program outline:

int main() {
    int length, queries;
    std::cin >> length >> queries;
    for (int i = 1; i <= length; ++i) std::cin >> array[i];
    initialize(1, 1, length);
    for (int i = 1; i <= queries; ++i) {
        int type;
        std::cin >> type;
        if (type == 1) {
            int start, end, value;
            std::cin >> start >> end >> value;
            updateRange(1, 1, length, start, end, {value});
        } else {
            int start, end;
            std::cin >> start >> end;
            auto result = queryRange(1, 1, length, start, end);
            std::cout << result.maxValue << '\n';
        }
    }
    return 0;
}

Tree construction initializes each node's lazy value. Unlike data initialization which occurs at leaves, lazy values must be initialized for every node.

void initialize(int nodeId, int left, int right) {
    tree[nodeId].lazy = {0};
    if (left == right) {
        tree[nodeId].info = {array[left]};
    } else {
        int mid = (left + right) / 2;
        initialize(nodeId * 2, left, mid);
        initialize(nodeId * 2 + 1, mid + 1, right);
        merge(nodeId);
    }
}

Query function applies pending updates before descending into subtrees.

Data queryRange(int nodeId, int left, int right, int queryLeft, int queryRight) {
    if (left >= queryLeft && right <= queryRight) {
        return tree[nodeId].info;
    } else {
        propagate(nodeId);
        int mid = (left + right) / 2;
        if (queryRight <= mid) 
            return queryRange(nodeId * 2, left, mid, queryLeft, queryRight);
        else if (queryLeft > mid) 
            return queryRange(nodeId * 2 + 1, mid + 1, right, queryLeft, queryRight);
        else 
            return queryRange(nodeId * 2, left, mid, queryLeft, mid) + 
                   queryRange(nodeId * 2 + 1, mid + 1, right, mid + 1, queryRight);
    }
}

Range updates traverse the tree, applying tags along the path. Before recursion, parent nodes' tags are pushed down to ensure correctness. After recursion, node data is updated.

void updateRange(int nodeId, int left, int right, int updateLeft, int updateRight, Update tag) {
    if (left >= updateLeft && right <= updateRight) {
        applyTag(nodeId, tag);
    } else {
        propagate(nodeId);
        int mid = (left + right) / 2;
        if (updateRight <= mid)
            updateRange(nodeId * 2, left, mid, updateLeft, updateRight, tag);
        else if (updateLeft > mid)
            updateRange(nodeId * 2 + 1, mid + 1, right, updateLeft, updateRight, tag);
        else {
            updateRange(nodeId * 2, left, mid, updateLeft, mid, tag);
            updateRange(nodeId * 2 + 1, mid + 1, right, mid + 1, updateRight, tag);
        }
        merge(nodeId);
    }
}

Key differences between basic and lazy segment trees lie in:

1. Presence of pushdown calls in query functions.
2. Tag management during tree construction and updates.

The fundamental approach remains consistent—define required data and update structures, then implement they interaction through well-defined operations.