洛谷P1438：如何高效维护区间等差数列更新
一、问题本质分析
题目要求我们维护一个数列，支持两种操作：1) 在区间[l,r]上加上一个等差数列；2) 查询某个位置的值。关键在于如何高效处理区间等差数列更新。
二、核心算法选择
三、关键技术点详解
线段树节点设计：
等差数列更新：
计算区间内等差数列的和
根据子区间位置调整首项
标记下传策略：
左子树直接继承k和d
右子树需要调整首项k' = k + d*len
查询优化：
单点查询时下传标记
直接返回叶子节点的值
四、代码实现
#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;
}五学习价值
通过这个题目可以掌握：
线段树的高级应用
懒标记的设计技巧
等差数列的数学性质应用
区间更新问题的通用解法
原创内容 转载请注明出处
