左边可以得到某个信息，右边可以得到某个信息，父节点的信息可以通过左右子信息在O(1)时间内整合得到的可以使用线段树。

    1. public class Code_SegmentTree {
    3.     // 线段树，时间复杂度logN，用于区间内更新，增加，查询
    4.     public static class SegmentTree {
    6.         // arr[]为原序列的信息从0开始，但在arr里是从1开始的
    7.         // sum[]模拟线段树维护区间和
    8.         // lazy[]为累加和懒惰标记
    9.         // change[]为更新的值
    10.         // update[]为更新慵懒标记
    12.         private int MAXN;
    13.         private int[] arr; // 缓的数组，原数组的备份数组
    14.         private int[] sum; // 累加和数组，
    15.         private int[] lazy;// 懒信息
    17.         // 更新相关的数组
    18.         private int[] change;      // 一个范围上的值变成了啥
    19.         private boolean[] update;  // 区分更新值的标记true表示change对应位置为更新的数，false表示该位置没更新无效。
    21.         // 
    22.         public SegmentTree(int[] origin) {
    23.             MAXN = origin.length + 1;
    24.             arr = new int[MAXN]; // arr[0] 不用 从1开始使用
    25.             for (int i = 1; i < MAXN; i++) {
    26.                 arr[i] = origin[i - 1];
    27.             }
    28.             sum = new int[MAXN << 2]; // 用来支持脑补概念中，某一个范围的累加和信息，原数组*4
    29.             lazy = new int[MAXN << 2]; // 用来支持脑补概念中，某一个范围沒有往下傳遞的纍加任務
    30.             change = new int[MAXN << 2]; // 用来支持脑补概念中，某一个范围有没有更新操作的任务
    31.             update = new boolean[MAXN << 2]; // 用来支持脑补概念中，某一个范围更新任务，更新成了什么
    32.         }
    34.         // 根据rt左右孩子的值，计算当前节点的sum数组值
    35.         private void pushUp(int rt) {
    36.             sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; // i*2  i*2+1
    37.         }
    39.         // 之前的，所有懒增加，和懒更新，从父范围，发给左右两个子范围
    40.         // 分发策略是什么
    41.         // rt 表示父节点
    42.         // ln表示左子树元素结点个数，rn表示右子树结点个数
    43.         private void pushDown(int rt, int ln, int rn) {
    44.             // 下发更新任务
    45.             if (update[rt]) {
    46.                 // 左右两个孩子都更新
    47.                 update[rt << 1] = true;
    48.                 update[rt << 1 | 1] = true;
    49.                 change[rt << 1] = change[rt];
    50.                 change[rt << 1 | 1] = change[rt];
    52.                 // 清空左右两个孩子的懒信息
    53.                 lazy[rt << 1] = 0;
    54.                 lazy[rt << 1 | 1] = 0;
    55.                 // 重新设置累加和信息
    56.                 sum[rt << 1] = change[rt] * ln;
    57.                 sum[rt << 1 | 1] = change[rt] * rn;
    58.                 update[rt] = false;
    59.             }
    60.             // 下发增加任务，懒数组更新，
    61.             if (lazy[rt] != 0) {
    62.                 // 左孩子累加和数组和懒数组更新
    63.                 lazy[rt << 1] += lazy[rt];
    64.                 sum[rt << 1] += lazy[rt] * ln;
    65.                 // 右孩子累加和和数组更新
    66.                 lazy[rt << 1 | 1] += lazy[rt];
    67.                 sum[rt << 1 | 1] += lazy[rt] * rn;
    68.                 // 清空父节点rt的懒信息
    69.                 lazy[rt] = 0;
    70.             }
    71.         }
    73.         // 在初始化阶段，先把sum数组，填好
    74.         // 在arr[l~r]范围上，去build，1~N，
    75.         // rt : 这个范围在sum中的下标
    76.         public void build(int l, int r, int rt) {
    77.             if (l == r) {
    78.                 sum[rt] = arr[l];
    79.                 return;
    80.             }
    81.             int mid = (l + r) >> 1;  // 找到中位数
    82.             build(l, mid, rt << 1); // 左孩子范围上build
    83.             build(mid + 1, r, rt << 1 | 1); // 右孩子范围上build
    84.             pushUp(rt);   // 计算sum数组rt位置的值
    85.         }
    87.         // L~R  所有的值变成C
    88.         // l~r  rt，当前来到l,r上，对应下表rt
    89.         public void update(int L, int R, int C, int l, int r, int rt) {
    90.             // 任务包含所有的值，有更新信息
    91.             if (L <= l && r <= R) {
    92.                 update[rt] = true;
    93.                 change[rt] = C;
    94.                 // 设置新的累加和
    95.                 sum[rt] = C * (r - l + 1);
    96.                 // 对应的懒数组位置清空
    97.                 lazy[rt] = 0;
    98.                 return;
    99.             }
    100.             // 当前任务躲不掉，无法懒更新，要往下发
    101.             int mid = (l + r) >> 1;
    102.             pushDown(rt, mid - l + 1, r - mid);
    103.             if (L <= mid) {
    104.                 update(L, R, C, l, mid, rt << 1);
    105.             }
    106.             if (R > mid) {
    107.                 update(L, R, C, mid + 1, r, rt << 1 | 1);
    108.             }
    109.             pushUp(rt);
    110.         }
    112.         // L~R, C 任务！L-R范围上每个值都加C，L,R,C在递归过程中不变
    113.         // rt，l~r，当前来到rt格子， 表示范围，l-r上的累加和
    114.         public void add(int L, int R, int C, int l, int r, int rt) {
    115.             // 任务如果把此时的范围全包了！
    116.             if (L <= l && r <= R) {
    117.                 sum[rt] += C * (r - l + 1);  // 更新l-r上的累加和
    118.                 lazy[rt] += C;               // 懒数组更新
    119.                 return;
    120.             }
    121.             // 任务没有把此时的范围全包！懒不住，任务下发
    122.             // l  r  mid = (l+r)/2
    123.             int mid = (l + r) >> 1;
    124.             pushDown(rt, mid - l + 1, r - mid);  // 下发一层任务
    125.             // L~R  派发新任务，
    126.             if (L <= mid) { // 如果任务需要发给左边
    127.                 // 左侧执行新任务
    128.                 add(L, R, C, l, mid, rt << 1);
    129.             }
    130.             if (R > mid) { // 如果任务需要发给右边
    131.                 // 右侧执行新任务
    132.                 add(L, R, C, mid + 1, r, rt << 1 | 1);
    133.             }
    134.             // 更新自己的累加和
    135.             pushUp(rt);
    136.         }
    138.         // 1~6 累加和是多少？ 1~8 rt
    139.         public long query(int L, int R, int l, int r, int rt) {
    140.             if (L <= l && r <= R) {
    141.                 return sum[rt];
    142.             }
    143.             int mid = (l + r) >> 1;
    144.             // 下发任务，为了配合add和update需要进行任务派发。
    145.             pushDown(rt, mid - l + 1, r - mid);
    146.             long ans = 0;
    147.             if (L <= mid) {
    148.                 ans += query(L, R, l, mid, rt << 1);
    149.             }
    150.             if (R > mid) {
    151.                 ans += query(L, R, mid + 1, r, rt << 1 | 1);
    152.             }
    153.             return ans;
    154.         }
    156.     }
    158.     // 纯暴力方法---测试使用  时间复杂度logN
    159.     public static class Right {
    160.         public int[] arr;
    161.         public Right(int[] origin) {
    162.             arr = new int[origin.length + 1];
    163.             for (int i = 0; i < origin.length; i++) {
    164.                 arr[i + 1] = origin[i];
    165.             }
    166.         }
    167.         public void update(int L, int R, int C) {
    168.             for (int i = L; i <= R; i++) {
    169.                 arr[i] = C;
    170.             }
    171.         }
    172.         public void add(int L, int R, int C) {
    173.             for (int i = L; i <= R; i++) {
    174.                 arr[i] += C;
    175.             }
    176.         }
    177.         public long query(int L, int R) {
    178.             long ans = 0;
    179.             for (int i = L; i <= R; i++) {
    180.                 ans += arr[i];
    181.             }
    182.             return ans;
    183.         }
    184.     }
    186.     public static int[] genarateRandomArray(int len, int max) {
    187.         int size = (int) (Math.random() * len) + 1;
    188.         int[] origin = new int[size];
    189.         for (int i = 0; i < size; i++) {
    190.             origin[i] = (int) (Math.random() * max) - (int) (Math.random() * max);
    191.         }
    192.         return origin;
    193.     }
    195.     public static boolean test() {
    196.         int len = 100;
    197.         int max = 1000;
    198.         int testTimes = 5000;
    199.         int addOrUpdateTimes = 1000;
    200.         int queryTimes = 500;
    201.         for (int i = 0; i < testTimes; i++) {
    202.             int[] origin = genarateRandomArray(len, max);
    203.             SegmentTree seg = new SegmentTree(origin);
    204.             int S = 1;
    205.             int N = origin.length;
    206.             int root = 1;
    207.             seg.build(S, N, root);
    208.             Right rig = new Right(origin);
    209.             for (int j = 0; j < addOrUpdateTimes; j++) {
    210.                 int num1 = (int) (Math.random() * N) + 1;
    211.                 int num2 = (int) (Math.random() * N) + 1;
    212.                 int L = Math.min(num1, num2);
    213.                 int R = Math.max(num1, num2);
    214.                 int C = (int) (Math.random() * max) - (int) (Math.random() * max);
    215.                 if (Math.random() < 0.5) {
    216.                     seg.add(L, R, C, S, N, root);
    217.                     rig.add(L, R, C);
    218.                 } else {
    219.                     seg.update(L, R, C, S, N, root);
    220.                     rig.update(L, R, C);
    221.                 }
    222.             }
    223.             for (int k = 0; k < queryTimes; k++) {
    224.                 int num1 = (int) (Math.random() * N) + 1;
    225.                 int num2 = (int) (Math.random() * N) + 1;
    226.                 int L = Math.min(num1, num2);
    227.                 int R = Math.max(num1, num2);
    228.                 long ans1 = seg.query(L, R, S, N, root);
    229.                 long ans2 = rig.query(L, R);
    230.                 if (ans1 != ans2) {
    231.                     return false;
    232.                 }
    233.             }
    234.         }
    235.         return true;
    236.     }
    238.     public static void main(String[] args) {
    239.         int[] origin = { 2, 1, 1, 2, 3, 4, 5 };
    240.         SegmentTree seg = new SegmentTree(origin);
    241.         int S = 1; // 整个区间的开始位置，规定从1开始，不从0开始 -> 固定
    242.         int N = origin.length; // 整个区间的结束位置，规定能到N，不是N-1 -> 固定
    243.         int root = 1; // 整棵树的头节点位置，规定是1，不是0 -> 固定
    244.         int L = 2; // 操作区间的开始位置 -> 可变
    245.         int R = 5; // 操作区间的结束位置 -> 可变
    246.         int C = 4; // 要加的数字或者要更新的数字 -> 可变
    247.         // 区间生成，必须在[S,N]整个范围上build
    248.         seg.build(S, N, root);
    249.         // 区间修改，可以改变L、R和C的值，其他值不可改变
    250.         seg.add(L, R, C, S, N, root);
    251.         // 区间更新，可以改变L、R和C的值，其他值不可改变
    252.         seg.update(L, R, C, S, N, root);
    253.         // 区间查询，可以改变L和R的值，其他值不可改变
    254.         long sum = seg.query(L, R, S, N, root);
    255.         System.out.println(sum);
    257.         System.out.println("对数器测试开始...");
    258.         System.out.println("测试结果 : " + (test() ? "通过" : "未通过"));
    259.     }
    261. }