线段树：一种支持范围整体修改和范围整体查询的数据结构
解决的问题范畴：
大范围信息可以只由左、右两侧信息加工出， 而不必遍历左右两个子范围的具体状况。
白话版解释就是：针对数组可以范围进行修改和查询。
假设，一个数组为 {5,1,3,7,8}。我们利用二叉树的性质可以过数组进行加工，按照区间的方式进行分类。
| 下标：0 | 1 | 2 | 3 | 4 | 5 |
| 数组：0忽略 | 5 | 1 | 3 | 7 | 8 |
这样的话，我们就可以利用二叉树的性质，构建一个新的结构，来进行范围统计了。如下：
假设，此时我们需要统计的是区间的累加和信息，那么按照这个结构就可以推算出来如下信息：
如果，把这些累加和信息存储在数组里面，得到如下信息：
利用二叉树层序遍历结构存储：
| 下标:0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 忽略 | 24 | 9 | 15 | 6 | 3 | 7 | 8 | 5 | 1 |
如果查询1-5范围的话，直接把下标为1的24返回即可，如果查询1-3次话，直接返回下标为2的9.
也就是说，线段树查询范围越大，性能越高。
懒更新：
就是对区间范围的数据进行更新操作，比如对1-5区间每个数组都加2. 那么我们直接统计出子元素只有5个，24 + 5*2 = 34；即直接把数组下标为1的24变更为34即可。这种只更新区间，而并没有对子元素进行更新，这就是懒更新。
那可能有人会说，你更新了1-5区间，我此时要查询1-3区间怎么办？
所谓的懒更新，只是在你使用到的时候更新，并不是不更新。你更新了1-5区间范围的累加和，我此时查询1-3范围，我们在查询的时候就需要知道1-5范围是否有懒更新情况，如果有就下放给左、右子节点，把左右子节点也给更新了。
理论说了这么多，代码到底该如何写呢？下面贴出3个版本。分别是新增功能、添加查询、
添加重置功能。比较起来更直观：
新增：
package code04.线段树_02;
public class SegmentTree1_add {
//构建从下标1开始的新数组，为了使用二叉树的性质
int[] arr;
//汇总区间值
int[] sum;
//懒更新数组
int[] lazy;
public SegmentTree1_add(int[] origin)
{
int size = origin.length;
arr = new int[size+1];
sum = new int[size*4];
lazy = new int[size*4];
//为了使用二叉树的性质，需要构建一个从1开始的新数组
for (int i = 1; i <= size; i++) {
arr[i] = origin[i-1];
}
}
//根据业务需求，需要构建线段树范围值（可以是累加和、也可以是max，视业务而定）
public void build (int left, int right, int curIndex)
{
//只剩1个数
if (left == right) {
sum[curIndex] = arr[left];
return;
}
int mid = (left + right)/2;
//左子树， curIndex代表当前节点的下标。 curIndex*2代表当前节点curIndex的左孩子
build(left, mid, curIndex*2);
//右子树, curIndex*2 + 1代表当前节点curIndex的右孩子
build(mid + 1, right, curIndex*2+1);
//汇总
collect(curIndex);
}
//汇总左、右孩子的累加和
public void collect(int curIndex) {
sum[curIndex] = sum[curIndex * 2] + sum[curIndex * 2 + 1];
}
/**
* @param left 代表数组范围区间的开始位置
* @param right 代表数组范围区间的结束位置
* @param start 任务开始位置
* @param end 任务结束位置
* @param value 从start到end范围之间，每个数加value
*/
public void add (int left, int right, int curIndex, int start, int end, int value)
{
//代表任务需要更新 start 到 end区间
//而 left 到 right 完全被任务的start到end包含。
// 直接更新汇总数据, 具体的子数组暂不更新
if (start <= left && right <= end) {
//统计left到right之间数字个数，每个数都增加 value
//区间更新，需要原有的sum[curIndex] 加上 新增的数值
sum[curIndex] += (right - left + 1) * value;
//此时，只是更新了区间汇总数据; 提升了时间复杂度；但是，
//区间内的实际数字并没有实际更新。因此需要记录下这一次操作
lazy[curIndex] = value;
return;
}
//假设数组长度为10，当前区间为1-5，我们需要更新2-6，也就是说上方逻辑包
//包不住；此时，原有的懒更新的数组记录的数据需要下放的子区间
int mid = (left + right)/2;
//下放之前lazy记录的数据, 有可能lazy没有数据
pushDown(curIndex, mid - left + 1, right - mid);
//更新左孩子区间
if (start <= mid) {
add(left, mid, curIndex*2, start, end, value);
}
//更新右孩子区间
if (end > mid) {
add(mid + 1, right, curIndex*2 + 1, start, end, value);
}
//左、右孩子区间都更新过了，需要汇总当前curIndex对应的区间汇总数据了
collect(curIndex);
}
public void pushDown(int curIndex, int leftChildren, int righChildren)
{
//如果之前有懒更新, 那么把懒更新数组到下一层区间去更新
if (lazy[curIndex] != 0) {
//左孩子区间值更新
sum[curIndex * 2] += leftChildren * lazy[curIndex];
//左孩子并没有全部更新，需要记录懒更新信息
lazy[curIndex*2] += lazy[curIndex];
//右孩子区间值更新
sum[curIndex * 2 + 1] += righChildren * lazy[curIndex];
lazy[curIndex*2+1] += lazy[curIndex];
//原有父区间重置
lazy[curIndex] = 0;
}
}
public static void main(String[] args) {
int[] aa = {5,1,3,7,8};
SegmentTree1_add ss = new SegmentTree1_add(aa);
int left = 1;
int right = aa.length;
int root = 1;
ss.build(left, right, root);
//1-5区间全部加2
ss.add(left, right, root, 1, 5, 2);
System.out.println("over");
}
}
增添查询：
package code04.线段树_02;
public class SegmentTree2_query {
//构建从下标1开始的新数组，为了使用二叉树的性质
int[] arr;
//汇总区间值
int[] sum;
//懒更新数组
int[] lazy;
public SegmentTree2_query(int[] origin)
{
int size = origin.length;
arr = new int[size+1];
sum = new int[size*4];
lazy = new int[size*4];
//为了使用二叉树的性质，需要构建一个从1开始的新数组
for (int i = 1; i <= size; i++) {
arr[i] = origin[i-1];
}
}
//根据业务需求，需要构建线段树范围值（可以是累加和、也可以是max，视业务而定）
public void build (int left, int right, int curIndex)
{
//只剩1个数
if (left == right) {
sum[curIndex] = arr[left];
return;
}
int mid = (left + right)/2;
//左子树， curIndex代表当前节点的下标。 curIndex*2代表当前节点curIndex的左孩子
build(left, mid, curIndex*2);
//右子树, curIndex*2 + 1代表当前节点curIndex的右孩子
build(mid + 1, right, curIndex*2+1);
//汇总
collect(curIndex);
}
//汇总左、右孩子的累加和
public void collect(int curIndex) {
sum[curIndex] = sum[curIndex * 2] + sum[curIndex * 2 + 1];
}
/**
* @param left 代表数组范围区间的开始位置
* @param right 代表数组范围区间的结束位置
* @param start 任务开始位置
* @param end 任务结束位置
* @param value 从start到end范围之间，每个数加value
*
* 区间范围新增、删除 value
*/
public void add (int left, int right, int curIndex, int start, int end, int value)
{
//代表任务需要更新 start 到 end区间
//而 left 到 right 完全被任务的start到end包含。
// 直接更新汇总数据, 具体的子数组暂不更新
if (start <= left && right <= end) {
//统计left到right之间数字个数，每个数都增加 value
//区间更新，需要原有的sum[curIndex] 加上 新增的数值
sum[curIndex] += (right - left + 1) * value;
//此时，只是更新了区间汇总数据; 提升了时间复杂度；但是，
//区间内的实际数字并没有实际更新。因此需要记录下这一次操作
lazy[curIndex] = value;
return;
}
//假设数组长度为10，当前区间为1-5，我们需要更新2-6，也就是说上方逻辑包
//包不住；此时，原有的懒更新的数组记录的数据需要下放的子区间
int mid = (left + right)/2;
//下放之前lazy记录的数据, 有可能lazy没有数据
pushDown(curIndex, mid - left + 1, right - mid);
//更新左孩子区间
if (start <= mid) {
add(left, mid, curIndex*2, start, end, value);
}
//更新右孩子区间
if (end > mid) {
add(mid + 1, right, curIndex*2 + 1, start, end, value);
}
//左、右孩子区间都更新过了，需要汇总当前curIndex对应的区间汇总数据了
collect(curIndex);
}
public void pushDown(int curIndex, int leftChildren, int righChildren)
{
//如果之前有懒更新, 那么把懒更新数组到下一层区间去更新
if (lazy[curIndex] != 0) {
//左孩子区间值更新
sum[curIndex * 2] += leftChildren * lazy[curIndex];
//左孩子并没有全部更新，需要记录懒更新信息
lazy[curIndex*2] += lazy[curIndex];
//右孩子区间值更新
sum[curIndex * 2 + 1] += righChildren * lazy[curIndex];
lazy[curIndex*2+1] += lazy[curIndex];
//原有父区间重置
lazy[curIndex] = 0;
}
}
//新增查询功能
/**
* @param left 代表数组范围区间的开始位置
* @param right 代表数组范围区间的结束位置
* @param start 任务开始位置
* @param end 任务结束位置
*
* 在 left 到 right之间，查询 start到end 区间数据和
*/
public int query(int left, int right, int curIndex, int start, int end)
{
if (start <= left && end >= right) {
return sum[curIndex];
}
int ans = 0;
int mid = (left + right)/2;
//防止部分区间懒更新。 比如1-5范围懒更新记录了数据，但是查询1-4范围。此时数据不正确
pushDown(curIndex, mid - left + 1, right - mid);
if (left < mid) {
ans += query(left, mid, curIndex * 2, start, end);
}
if (right > mid) {
ans += query(mid + 1, right, curIndex * 2 + 1, start, end);
}
return ans;
}
public static void main(String[] args) {
int[] aa = {5,1,3,7,8};
SegmentTree2_query ss = new SegmentTree2_query(aa);
int left = 1;
int right = aa.length;
int root = 1;
ss.build(left, right, root);
int ans = ss.query(left, right, root, 1, 4);
System.out.println("添加数据之前： " + ans);
//1-5区间全部加2
ss.add(left, right, root, 1, 5, 2);
//查询1-4区间
int ans2 = ss.query(left, right, root, 1, 4);
System.out.println("添加数据以后： " + ans2);
}
}
重置：
package code04.线段树_02;
import java.sql.Struct;
public class SegmentTree2_reset {
//构建从下标1开始的新数组，为了使用二叉树的性质
int[] arr;
//汇总区间值
int[] sum;
//懒更新数组
int[] lazy;
//记录是否重置
boolean[] reset;
//记录重置的值
int[] change;
public SegmentTree2_reset(int[] origin)
{
int size = origin.length;
arr = new int[size+1];
sum = new int[size*4];
lazy = new int[size*4];
reset = new boolean[size*4];
change = new int[size*4];
//为了使用二叉树的性质，需要构建一个从1开始的新数组
for (int i = 1; i <= size; i++) {
arr[i] = origin[i-1];
}
}
//根据业务需求，需要构建线段树范围值（可以是累加和、也可以是max，视业务而定）
public void build (int left, int right, int curIndex)
{
//只剩1个数
if (left == right) {
sum[curIndex] = arr[left];
return;
}
int mid = (left + right)/2;
//左子树， curIndex代表当前节点的下标。 curIndex*2代表当前节点curIndex的左孩子
build(left, mid, curIndex*2);
//右子树, curIndex*2 + 1代表当前节点curIndex的右孩子
build(mid + 1, right, curIndex*2+1);
//汇总
collect(curIndex);
}
//汇总左、右孩子的累加和
public void collect(int curIndex) {
sum[curIndex] = sum[curIndex * 2] + sum[curIndex * 2 + 1];
}
/**
* @param left 代表数组范围区间的开始位置
* @param right 代表数组范围区间的结束位置
* @param start 任务开始位置
* @param end 任务结束位置
* @param value 从start到end范围之间，每个数加value
*
* 区间范围新增、删除 value
*/
public void add (int left, int right, int curIndex, int start, int end, int value)
{
//代表任务需要更新 start 到 end区间
//而 left 到 right 完全被任务的start到end包含。
// 直接更新汇总数据, 具体的子数组暂不更新
if (start <= left && right <= end) {
//统计left到right之间数字个数，每个数都增加 value
//区间更新，需要原有的sum[curIndex] 加上 新增的数值
sum[curIndex] += (right - left + 1) * value;
//此时，只是更新了区间汇总数据; 提升了时间复杂度；但是，
//区间内的实际数字并没有实际更新。因此需要记录下这一次操作
lazy[curIndex] = value;
return;
}
//假设数组长度为10，当前区间为1-5，我们需要更新2-6，也就是说上方逻辑包
//包不住；此时，原有的懒更新的数组记录的数据需要下放的子区间
int mid = (left + right)/2;
//下放之前lazy记录的数据, 有可能lazy没有数据
pushDown(curIndex, mid - left + 1, right - mid);
//更新左孩子区间
if (start <= mid) {
add(left, mid, curIndex*2, start, end, value);
}
//更新右孩子区间
if (end > mid) {
add(mid + 1, right, curIndex*2 + 1, start, end, value);
}
//左、右孩子区间都更新过了，需要汇总当前curIndex对应的区间汇总数据了
collect(curIndex);
}
public void pushDown(int curIndex, int leftChildren, int righChildren)
{
//重置
if (reset[curIndex]) {
//左、右孩子重置
reset[curIndex * 2] = true;
reset[curIndex * 2 + 1] = true;
//左右孩子重置的值
change[curIndex * 2] = change[curIndex];
change[curIndex * 2 + 1] = change[curIndex];
//左右孩子的区间值也需要重置
sum[curIndex * 2] = change[curIndex] * leftChildren;
sum[curIndex * 2 + 1] = change[curIndex] * righChildren;
//全部都重置了，之前懒更新数据就不关注了;就算是更新完再重置，还是一样的
lazy[curIndex * 2] = 0;
lazy[curIndex * 2 + 1] = 0;
//更新curIndex节点
reset[curIndex] = false;
}
//如果之前有懒更新, 那么把懒更新数组到下一层区间去更新
if (lazy[curIndex] != 0) {
//左孩子区间值更新
sum[curIndex * 2] += leftChildren * lazy[curIndex];
//左孩子并没有全部更新，需要记录懒更新信息
lazy[curIndex*2] += lazy[curIndex];
//右孩子区间值更新
sum[curIndex * 2 + 1] += righChildren * lazy[curIndex];
lazy[curIndex*2+1] += lazy[curIndex];
//原有父区间重置
lazy[curIndex] = 0;
}
}
//新增查询功能
/**
* @param left 代表数组范围区间的开始位置
* @param right 代表数组范围区间的结束位置
* @param start 任务开始位置
* @param end 任务结束位置
*
* 在 left 到 right之间，查询 start到end 区间数据和
*/
public int query(int left, int right, int curIndex, int start, int end)
{
if (start <= left && end >= right) {
return sum[curIndex];
}
int ans = 0;
int mid = (left + right)/2;
//防止部分区间懒更新。 比如1-5范围懒更新记录了数据，但是查询1-4范围。此时数据不正确
pushDown(curIndex, mid - left + 1, right - mid);
if (left < mid) {
ans += query(left, mid, curIndex * 2, start, end);
}
if (right > mid) {
ans += query(mid + 1, right, curIndex * 2 + 1, start, end);
}
return ans;
}
//重置start到end区域的值为 value
public void resetZone(int left, int right, int curIndex, int start, int end, int value)
{
if (start <= left && end >= right) {
reset[curIndex] = true;
change[curIndex] = value;
//重置，无论之前add是什么数据，一切回归默认值
lazy[curIndex] = 0;
//重置后，所有孩子都是默认值value
sum[curIndex] = (right - left + 1) * value;
return;
}
int mid = (left + right)/2;
//防止部分区间懒更新。 比如1-5范围懒更新记录了数据，但是查询1-4范围。此时数据不正确
pushDown(curIndex, mid - left + 1, right - mid);
if (left < mid) {
resetZone(left, mid, curIndex * 2, start, end, value);
}
if (right > mid) {
resetZone(mid + 1, right, curIndex * 2 + 1, start, end, value);
}
collect(curIndex);
}
public static void main(String[] args) {
int[] aa = {5,1,3,7,8};
SegmentTree2_reset ss = new SegmentTree2_reset(aa);
int left = 1;
int right = aa.length;
int root = 1;
ss.build(left, right, root);
int ans = ss.query(left, right, root, 1, 4);
System.out.println("添加数据之前： " + ans);
//1-5区间全部加2
ss.add(left, right, root, 1, 5, 2);
//查询1-4区间
int ans2 = ss.query(left, right, root, 1, 4);
System.out.println("添加数据以后： " + ans2);
//重置2-4范围
ss.resetZone(left, right, root, 2, 4, 2);
//查询1-4区间
int ans3 = ss.query(left, right, root, 1, 4);
System.out.println("重置以后 ：" + ans3);
}
}
可能有人也会说，这种数组结构，算累加和。我用前缀数组技术也完全可以解决。是的，但是线段树解决的问题，并不是前缀树组一定能够解决的。而且线段树的时间复杂度也很低。
线段树的时间复杂度为 O(logN)。
