线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。
线段树思想
引言：给定一个数组，不断询问数组区间[L, R]的和 或 改变某一位置的值，怎么实现？
实现方式：普通的前缀和计算时间复杂度是O(n)，较大；而树状数组可以在log(n)复杂度下实现。而现在，还有另一种方式可以在相同时间复杂度实现，且可以实现更复杂的区间操作，即线段树。
线段树的构建：给定一个数组arr，根据其长度来建立（二叉搜索树的）根节点，而每个节点都是一个区间的和（叶节点对应arr数组值）。按二分方式从根节点不断扩展建树，可得到如下图：
线段树代码构建思路：从根节点开始编号，用数组来表示一棵满二叉树（不存在的节点留有位置），这样把节点依次存进去，然后可以清楚的发现每个节点（编号为node）的左孩子编号是 2×node+1，右孩子编号是 2×node+2。（node表示构建树的下标，其他的为原数组arr的下标）
private static void build_tree(int[] arr, int[] tree,
int node, int start, int end) {
if (start == end) {
tree[node] = arr[start];
return;
}
int mid = (start + end) / 2;
int left_node = 2 * node + 1;
int right_node = 2 * node + 2;
build_tree(arr, tree, left_node, start, mid);
build_tree(arr, tree, right_node, mid+1, end);
tree[node] = tree[left_node] + tree[right_node];
}
线段树的查询：比如查询区间[2, 5]的和，从根节点出发，根据二分的性质可以依次遍历此二叉树，找到符合的节点再求和即可。
private static int query_tree(int[] arr, int[] tree,
int node, int start, int end,
int L, int R){
if (R < start || L > end) { // 越界
return 0;
}
else if (start >= L && end <= R) { // 该区间完全被查询区间包含
return tree[node];
}
else if (start == end) { // 查询到叶节点
return tree[node];
}
int mid = (start + end) / 2;
int left_node = 2 * node + 1;
int right_node = 2 * node + 2;
int sum_left = query_tree(arr, tree, left_node, start, mid, L, R);
int sum_right = query_tree(arr, tree, right_node, mid+1, end, L, R);
return sum_left + sum_right;
}
线段树的更新：比如要修改arr[4]=6，那么从图中可以看出，除了要修改叶节点外，还要从下开始往上递归的修改其父节点。（当然还要修改原始数组arr的值）
private static void update_tree(int[] arr, int[] tree,
int node, int start, int end,
int index, int val) {
if (start == end) {
arr[index] = val;
tree[node] = val;
return;
}
int mid = (start + end) / 2;
int left_node = 2 * node + 1;
int right_node = 2 * node + 2;
if (index >= start && index <= mid) {
update_tree(arr, tree, left_node, start, mid, index, val);
}
else {
update_tree(arr, tree, right_node, mid+1, end, index, val);
}
tree[node] = tree[left_node] + tree[right_node];
}
完整代码验证
public class Main {
// 其他方法上述已有
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11};
int size = arr.length;
int[] tree = new int[size * 4];
build_tree(arr, tree, 0, 0, size-1);
update_tree(arr, tree, 0, 0, size-1, 4, 6);
for (int i=0; i<tree.length; i++) {
System.out.println(tree[i]);
}
int sum = query_tree(arr, tree, 0, 0, size-1, 2, 5);
System.out.println(sum);
}
}
区间更新，区间查询
线段树对于区间更新、区间查询具有相对简单的处理方法，无论是对区间的加减还是乘除操作。
其中包含一个重要的 lazy 标记，所谓 lazy 标记：就是在区间更新过程中，其父节点已经被更新且标记，那么子节点便不再进行更新操作，留给后续更新，它存储的就是更新操作的值。（即只记录没有被访问过的节点的值；若还有其他操作需要定义不同类型的lazy标记，可在学会本节体验）
而对应lazy标记的是push_down操作，它的作用就是将父节点记录的lazy值传递给直接子节点，并在传递完成后取消自己的标记并给子节点加上标记。该操作必须在访问子节点前完成。
其思路如上叙述，以下是模板代码：
完整代码（含解释）
import java.util.Scanner;
/**
* 区间查询，区间修改
* 测试：https://www.luogu.com.cn/problem/P3372
*/
public class Main{
static final int MAXN = 1000_005;
static long[] a = new long[MAXN]; // 原数组
static long[] lazy = new long[MAXN << 2]; // 记录每次更新时的值
static long[] tree = new long[MAXN << 2]; // 记录线段树的每一个节点
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int m = cin.nextInt();
for (int i=1; i<=n; i++){
a[i] = cin.nextInt();
}
build_tree(1, 1, n);
int opt, l, r, v;
while (m-- > 0){
opt = cin.nextInt();
switch (opt) {
case 1: { // 区间更新
l = cin.nextInt();
r = cin.nextInt();
v = cin.nextInt();
update_tree(l, r, 1, n, 1, v);
break;
}
case 2: { // 区间修改
l = cin.nextInt();
r = cin.nextInt();
System.out.println(query_tree(l, r, 1, n, 1));
break;
}
}
}
}
/**
* 区间查询
*/
private static long query_tree(int l, int r, int left, int right, int node) {
long res = 0;
if (l <= left && right <= r) { // 更新区间完全包含查询区间
return tree[node];
}
int mid = (left + right) >> 1;
push_down(node, left, right); // 每次向下查询时都将标记传递下去
if (l <= mid) { // 更新区间包含在左子树时
res += query_tree(l, r, left, mid, get_left_node(node));
}
if (r > mid) { // 更新区间包含在右子树时
res += query_tree(l, r, mid+1, right, get_right_node(node));
}
return res;
}
/**
* 区间更新
* @param l 更新区间的左端点
* @param r 更新区间的右端点
* @param left 查询区间的左端点
* @param right 查询区间的右端点
* @param node 当前节点下标
* @param val 增加的值
*/
private static void update_tree(int l, int r, int left, int right, int node, int val) {
if (r < left || l > right) { // 更新区间和查询区间没有交集
return;
}
if (l <= left && right <= r) { // 更新区间完全包含查询区间
tree[node] += val * (right - left + 1); // 更新当前节点值
lazy[node] += val; // 标记子节点需要更新的值
return;
}
// 需要查询子节点时传递父节点（当前节点）的标记
push_down(node, left, right);
int mid = (left + right) >> 1;
if (l <= mid) { // 更新区间包含在左子树时
update_tree(l, r, left, mid, get_left_node(node), val);
}
if (r > mid) { // 更新区间包含在右子树时
update_tree(l, r, mid+1, right, get_right_node(node), val);
}
// 更新当前节点的值
push_up(node);
}
/**
* 为子节点传递标记
* @param node 父节点下标
* @param left 查询区间左端点
* @param right 查询区间右端点
*/
private static void push_down(int node, int left, int right) {
int mid = (left + right) >> 1;
add_lazy(get_left_node(node), left, mid, lazy[node]);
add_lazy(get_right_node(node), mid+1, right, lazy[node]);
lazy[node] = 0; // 完成子节点标记后，取消当前节点标记
}
/**
* 更新子节点标记
* @param p 子节点下标
* @param left 查询区间左端点
* @param right 查询区间右端点
* @param val 父节点lazy值
*/
private static void add_lazy(int p, int left, int right, long val) {
lazy[p] += val;
tree[p] += (val * (right - left + 1));
}
/**
* 建树
*/
private static void build_tree(int node, int l, int r) {
lazy[node] = 0;
if (l == r) {
tree[node] = a[l];
return;
}
int mid = (l + r) >> 1;
build_tree(get_left_node(node), l, mid);
build_tree(get_right_node(node), mid+1, r);
push_up(node);
}
/**
* 计算非叶子节点的值
*/
private static void push_up(int p) {
tree[p] = tree[get_left_node(p)] + tree[get_right_node(p)];
}
/**
* 得到右节点
*/
private static int get_right_node(int x) {
return x << 1 | 1;
}
/**
* 得到左节点
*/
private static int get_left_node(int x) {
return x << 1;
}
}
网友评论