洛谷P1438题解：基于线段树的等差数列
3个月前 (07-12)
一、题目解读
洛谷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;
}五、总结
本解法通过线段树结合等差数列特性，巧妙利用“懒惰标记”减少冗余计算，实现高效区间更新。关键突破在于标记下传时，对子树k、d的传递公式推导需严谨考虑区间长度影响。此外，代码结构清晰，递归逻辑易扩展至其他区间修改场景。掌握此类优化技巧可显著提升算法竞赛中动态区间问题的解题效率。
原创内容 转载请注明出处
