一维动态前缀和（区修区查）
一维动态前缀和（区修区查）
线段树（Segment Tree）是一种支持区间修改和区间查询的数据结构。
它能在 的时间复杂度内完成区间操作，比树状数组更加灵活，是实现区间修改的理想选择。
基本概念
线段树的核心思想是：
- 将区间划分成多个子区间
- 每个节点维护一个区间的信息
- 使用懒标记处理区间修改
- 支持多种区间操作（和、最大值、最小值等）
实现方式
线段树的关键操作：
- build：构建线段树
- pushDown：下传懒标记
- update：区间修改
- query：区间查询
基本实现
class SegmentTree {
private:
vector<int> tree, lazy;
int n;
void pushDown(int node, int start, int end) {
if (lazy[node] != 0) {
int mid = (start + end) >> 1;
int leftNode = node * 2 + 1;
int rightNode = node * 2 + 2;
// 更新左子树
tree[leftNode] += lazy[node] * (mid - start + 1);
lazy[leftNode] += lazy[node];
// 更新右子树
tree[rightNode] += lazy[node] * (end - mid);
lazy[rightNode] += lazy[node];
lazy[node] = 0;
}
}
public:
SegmentTree(int size) : n(size) {
tree.resize(4 * n);
lazy.resize(4 * n);
}
void update(int node, int start, int end, int left, int right, int val) {
if (left > end || right < start) return;
if (left <= start && end <= right) {
tree[node] += val * (end - start + 1);
lazy[node] += val;
return;
}
pushDown(node, start, end);
int mid = (start + end) >> 1;
update(node * 2 + 1, start, mid, left, right, val);
update(node * 2 + 2, mid + 1, end, left, right, val);
tree[node] = tree[node * 2 + 1] + tree[node * 2 + 2];
}
int query(int node, int start, int end, int left, int right) {
if (left > end || right < start) return 0;
if (left <= start && end <= right) {
return tree[node];
}
pushDown(node, start, end);
int mid = (start + end) >> 1;
return query(node * 2 + 1, start, mid, left, right) +
query(node * 2 + 2, mid + 1, end, left, right);
}
};
class SegmentTree {
private int[] tree;
private int[] lazy;
private int n;
public SegmentTree(int size) {
n = size;
tree = new int[4 * n];
lazy = new int[4 * n];
}
private void pushDown(int node, int start, int end) {
if (lazy[node] != 0) {
int mid = (start + end) >> 1;
int leftNode = node * 2 + 1;
int rightNode = node * 2 + 2;
// 更新左子树
tree[leftNode] += lazy[node] * (mid - start + 1);
lazy[leftNode] += lazy[node];
// 更新右子树
tree[rightNode] += lazy[node] * (end - mid);
lazy[rightNode] += lazy[node];
lazy[node] = 0;
}
}
public void update(int node, int start, int end, int left, int right, int val) {
if (left > end || right < start) return;
if (left <= start && end <= right) {
tree[node] += val * (end - start + 1);
lazy[node] += val;
return;
}
pushDown(node, start, end);
int mid = (start + end) >> 1;
update(node * 2 + 1, start, mid, left, right, val);
update(node * 2 + 2, mid + 1, end, left, right, val);
tree[node] = tree[node * 2 + 1] + tree[node * 2 + 2];
}
public int query(int node, int start, int end, int left, int right) {
if (left > end || right < start) return 0;
if (left <= start && end <= right) {
return tree[node];
}
pushDown(node, start, end);
int mid = (start + end) >> 1;
return query(node * 2 + 1, start, mid, left, right) +
query(node * 2 + 2, mid + 1, end, left, right);
}
}
class SegmentTree:
def __init__(self, size):
self.n = size
self.tree = [0] * (4 * size)
self.lazy = [0] * (4 * size)
def push_down(self, node, start, end):
if self.lazy[node] != 0:
mid = (start + end) >> 1
left_node = node * 2 + 1
right_node = node * 2 + 2
# 更新左子树
self.tree[left_node] += self.lazy[node] * (mid - start + 1)
self.lazy[left_node] += self.lazy[node]
# 更新右子树
self.tree[right_node] += self.lazy[node] * (end - mid)
self.lazy[right_node] += self.lazy[node]
self.lazy[node] = 0
def update(self, node, start, end, left, right, val):
if left > end or right < start:
return
if left <= start and end <= right:
self.tree[node] += val * (end - start + 1)
self.lazy[node] += val
return
self.push_down(node, start, end)
mid = (start + end) >> 1
self.update(node * 2 + 1, start, mid, left, right, val)
self.update(node * 2 + 2, mid + 1, end, left, right, val)
self.tree[node] = self.tree[node * 2 + 1] + self.tree[node * 2 + 2]
def query(self, node, start, end, left, right):
if left > end or right < start:
return 0
if left <= start and end <= right:
return self.tree[node]
self.push_down(node, start, end)
mid = (start + end) >> 1
return (self.query(node * 2 + 1, start, mid, left, right) +
self.query(node * 2 + 2, mid + 1, end, left, right))
应用场景
线段树在很多问题中都有应用：
- 区间修改和查询
- 区间最值查询
- 区间统计问题
- 动态维护区间信息
- 扫描线算法
示例：区间加法
class Solution {
SegmentTree* st;
public:
vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
st = new SegmentTree(length);
// 执行所有更新操作
for (const auto& update : updates) {
int start = update[0];
int end = update[1];
int val = update[2];
st->update(0, 0, length-1, start, end, val);
}
// 查询每个位置的值
vector<int> result(length);
for (int i = 0; i < length; i++) {
result[i] = st->query(0, 0, length-1, i, i);
}
return result;
}
};
class Solution {
private SegmentTree st;
public int[] getModifiedArray(int length, int[][] updates) {
st = new SegmentTree(length);
// 执行所有更新操作
for (int[] update : updates) {
int start = update[0];
int end = update[1];
int val = update[2];
st.update(0, 0, length-1, start, end, val);
}
// 查询每个位置的值
int[] result = new int[length];
for (int i = 0; i < length; i++) {
result[i] = st.query(0, 0, length-1, i, i);
}
return result;
}
}
class Solution:
def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
st = SegmentTree(length)
# 执行所有更新操作
for start, end, val in updates:
st.update(0, 0, length-1, start, end, val)
# 查询每个位置的值
result = []
for i in range(length):
result.append(st.query(0, 0, length-1, i, i))
return result
时间复杂度
- 初始化：
- 区间修改：
- 区间查询：
- 空间复杂度：
线段树 vs 树状数组
优点：
- 支持区间修改
- 更加灵活
- 可以维护多种信息
缺点：
- 实现复杂
- 代码量大
- 常数较大
注意事项
- 正确处理懒标记
- 注意区间边界
- 合理分配数组大小
- 处理整数溢出
练习建议
- 实现基本的线段树操作
- 尝试不同的区间操作
- 解决区间统计问题
- 实现其他线段树变体
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。
