当前位置：首页 > 洛谷 > 洛谷P1438题解：基于线段树的等差数列

洛谷P1438题解：基于线段树的等差数列

5天前

一、题目解读

洛谷P1438题要求处理数列的区间更新与单点查询操作，其中更新方式为给定区间内元素按等差数列递增。传统暴力修改会因多次区间遍历导致超时，需设计高效数据结构——线段树，结合等差数列性质实现O(logN)复杂度解决方案。

二、解题思路

核心思想为利用线段树维护区间和、首项与公差，通过“懒惰标记”延迟更新，避免子树重复计算。每次区间修改时，仅传递增量k（首项增量）与d（公差增量）至对应节点，查询时通过公式还原原数列值。关键在于推导节点合并与标记下传时的数学逻辑，确保区间和正确更新。

三、解题步骤

1. 构建线段树：自顶向下递归，叶子节点存储单点值，非叶节点维护子区间和。

2. 懒惰标记下传（pushDown）：

○ 当节点存在未传递的k、d时，计算左子树更新后的sum、k、d，并调整右子树k（考虑左区间长度影响）。

○ 清空当前节点标记，避免重复更新。

3. 区间更新（rangeAdd）：

○ 递归至目标区间覆盖的节点，下传父节点标记后，更新当前节点k、d及sum。

4. 单点查询（query）：递归至目标点，沿途累加经过节点的sum。

四、代码与注释

#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; // 更新区间和（等差数列求和公式）
                
                // 调整右子树标记（考虑左区间对右区间首项的影响）
                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->l >= l && node->r <= r) { // 目标区间完全覆盖当前节点
            node->k += k; // 累加首项增量
            node->d += d; // 累加公差增量
            int len = node->r - node->l + 1; // 当前区间长度
            node->sum += k * len + d * len * (len - 1) / 2; // 更新区间和
        } else { // 区间部分覆盖，递归处理
            pushDown(node); // 下传父节点标记
            int mid = (node->l + node->r) / 2;
            if (l <= mid) update(node->left, l, r, k, d); // 左子树更新
            if (r > mid) 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); // 下传标记
        int mid = (node->l + node->r) / 2;
        return p <= mid? query(node->left, p) : 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;
}