洛谷P1438：如何高效维护区间等差数列更新

一、问题本质分析

题目要求我们维护一个数列，支持两种操作：1) 在区间[l,r]上加上一个等差数列；2) 查询某个位置的值。关键在于如何高效处理区间等差数列更新。

二、核心算法选择

1. ‌线段树‌：使用带懒标记的线段树维护区间信息

2. ‌等差数列性质‌：利用等差数列求和公式优化计算

3. ‌懒标记传递‌：设计特殊的标记下传策略处理等差数列

三、关键技术点详解

1. ‌线段树节点设计‌：

• 存储区间和、首项k、公差d

• 左右子树指针和区间范围

2. ‌等差数列更新‌：

• 计算区间内等差数列的和

• 根据子区间位置调整首项

3. ‌标记下传策略‌：

• 左子树直接继承k和d

• 右子树需要调整首项k' = k + d*len

4. ‌查询优化‌：

• 单点查询时下传标记

• 直接返回叶子节点的值

四、代码实现

#include <iostream>
#include <vector>
using namespACe std;

struct Node {
    long long sum;  // 区间和
    long long k;    // 首项
    long long d;    // 公差
    int l, r;       // 区间范围
    Node *left, *right;
    
    Node(int l, int r) : l(l), r(r), k(0), d(0), left(nullptr), right(nullptr) {}
};

class SegmentTree {
public:
    SegmentTree(const vector<int>& nums) {
        root = build(nums, 1, nums.size());
    }
    
    // 区间更新等差数列
    void rangeAdd(int l, int r, long long k, long long d) {
        update(root, l, r, k, d);
    }
    
    // 单点查询
    long long query(int p) {
        return query(root, p);
    }

private:
    Node* root;
    
    Node* build(const vector<int>& nums, int l, int r) {
        Node* node = new Node(l, r);
        if (l == r) {
            node->sum = nums[l-1];
            return node;
        }
        int mid = (l + r) / 2;
        node->left = build(nums, l, mid);
        node->right = build(nums, mid+1, r);
        node->sum = node->left->sum + node->right->sum;
        return node;
    }
    
    void pushDown(Node* node) {
        if (node->k != 0 || node->d != 0) {
            if (node->left) {
                int len = node->left->r - node->left->l + 1;
                node->left->k += node->k;
                node->left->d += node->d;
                node->left->sum += node->k * len + node->d * len * (len - 1) / 2;
                
                // 传递给右子树的k需要调整
                node->right->k += node->k + node->d * len;
                node->right->d += node->d;
                int r_len = node->right->r - node->right->l + 1;
                node->right->sum += (node->k + node->d * len) * r_len + node->d * r_len * (r_len - 1) / 2;
            }
            node->k = 0;
            node->d = 0;
        }
    }
    
    void update(Node* node, int l, int r, long long k, long long d) {
        if (node->r < l || node->l > r) return;
        if (l <= node->l && node->r <= r) {
            int len = node->r - node->l + 1;
            long long start = k + d * (node->l - l);
            node->k += start;
            node->d += d;
            node->sum += start * len + d * len * (len - 1) / 2;
            return;
        }
        pushDown(node);
        update(node->left, l, r, k, d);
        update(node->right, l, r, k, d);
        node->sum = node->left->sum + node->right->sum;
    }
    
    long long query(Node* node, int p) {
        if (node->l == node->r) {
            return node->sum;
        }
        pushDown(node);
        if (p <= node->left->r) {
            return query(node->left, p);
        } else {
            return query(node->right, p);
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    SegmentTree st(a);
    
    while (m--) {
        int opt;
        cin >> opt;
        if (opt == 1) {
            int l, r;
            long long k, d;
            cin >> l >> r >> k >> d;
            st.rangeAdd(l, r, k, d);
        } else {
            int p;
            cin >> p;
            cout << st.query(p) << '\n';
        }
    }
    
    return 0;
}

五学习价值

通过这个题目可以掌握：

1. 线段树的高级应用

2. 懒标记的设计技巧

3. 等差数列的数学性质应用

4. 区间更新问题的通用解法