To solve this problem, we need to efficiently handle range updates and range sum queries on an array. A segment tree with lazy propagation is the ideal data structure for this task, as it allows both operations to be performed in O(log n) time complexity.

Approach

1. Segment Tree Structure: The segment tree is built to store the sum of elements in each interval. Each node in the tree also maintains a lazy tag to defer range updates to child nodes until necessary.
2. Build Function: Constructs the segment tree from the input array. For leaf nodes, the value is the element itself. For internal nodes, the value is the sum of its left and right children.
3. Push Function: Propagates the lazy tag to the child nodes. This ensures that pending updates are applied before processing any queries or further updates on the child nodes.
4. Update Function: Applies a range update (add a value to all elements in a range). If the current node's interval is fully within the target range, the update is applied directly and the lazy tag is set. Otherwise, the lazy tag is pushed down and the update is recursively applied to the relevant child nodes.
5. Query Function: Computes the sum of elements in a given range. Similar to the update function, it pushes down any pending lazy updates before querying the child nodes.

Solution Code

#include <iostream>
using namespace std;

const int MAXN = 2e5 + 10;

struct Node {
    long long val;
    long long add;
} tree[4 * MAXN];

long long a[MAXN];

void build(int node, int l, int r) {
    tree[node].add = 0;
    if (l == r) {
        tree[node].val = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);
    tree[node].val = tree[2 * node].val + tree[2 * node + 1].val;
}

void push(int node, int l, int r) {
    if (tree[node].add == 0) return;
    int mid = (l + r) / 2;
    int left = 2 * node;
    int right_node = 2 * node + 1;

    tree[left].val += tree[node].add * (mid - l + 1);
    tree[left].add += tree[node].add;

    tree[right_node].val += tree[node].add * (r - mid);
    tree[right_node].add += tree[node].add;

    tree[node].add = 0;
}

void update(int node, int l, int r, int ul, int ur, long long x) {
    if (ur < l || ul > r) return;
    if (ul <= l && r <= ur) {
        tree[node].val += x * (r - l + 1);
        tree[node].add += x;
        return;
    }
    push(node, l, r);
    int mid = (l + r) / 2;
    update(2 * node, l, mid, ul, ur, x);
    update(2 * node + 1, mid + 1, r, ul, ur, x);
    tree[node].val = tree[2 * node].val + tree[2 * node + 1].val;
}

long long query(int node, int l, int r, int ql, int qr) {
    if (qr < l || ql > r) return 0;
    if (ql <= l && r <= qr) return tree[node].val;
    push(node, l, r);
    int mid = (l + r) / 2;
    return query(2 * node, l, mid, ql, qr) + query(2 * node + 1, mid + 1, r, ql, qr);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    build(1, 1, n);

    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r;
            long long x;
            cin >> l >> r >> x;
            update(1, 1, n, l, r, x);
        } else if (op == 2) {
            int l, r;
            cin >> l >> r;
            cout << query(1, 1, n, l, r) << '\n';
        }
    }

    return 0;
}

Explanation

• Segment Tree: The tree is built to cover all elements of the array. Each node represents an interval and stores the sum of elements in that interval.
• Lazy Propagation: This technique defers updates to child nodes until necessary, which optimizes the time complexity of range updates. The push function ensures that pending updates are applied before processing child nodes.
• Efficiency: Both range updates and range queries are handled in O(log n) time, making the solution efficient even for large input sizes (up to 200,000 elements and operations).

This approach ensures that we can handle the problem constraints efficiently and correctly. The use of long long prevents integer overflow, which is crucial for large sums. The input/output optimizations (ios::sync_with_stdio(false); and cin.tie(nullptr);) improve the speed of the solution for large inputs.

（免责声明：本文为本网站出于传播商业信息之目的进行转载发布，不代表本网站的观点及立场。本文所涉文、图、音视频等资料的一切权利和法律责任归材料提供方所有和承担。本网站对此资讯文字、图片等所有信息的真实性不作任何保证或承诺，亦不构成任何购买、投资等建议，据此操作者风险自担。） 本文为转载内容，授权事宜请联系原著作权人，如有侵权，请联系本网进行删除。