线段树思想拆解（下篇）

线段树思想拆解（下篇）

上篇回顾

到这里我们已经处理好了初始化以及添加方法，接下来实现范围的 query 方法

    public int query(int queryL, int queryR) {return query(queryL, queryR, 1, orgLength - 1, 1);}

到此为止通过借助 sum 数组，lazy 数组就已经实现了在范围内统一增加一个数值，查询范围总和的时间复杂度为 O(logN) 了，接下来要引入更新操作，对于更新操作我们需要再借助两个数组来维护更新的懒操作。

接上篇来讲，注意一下我们所有方法的 L 和 R 的范围都是指源数组的范围，即源数组是 8 个数字，则范围为 1-8 ， 而对于我们的逻辑线段树数组是通过 index 进行计算得到表示范围的节点数组槽位。

增加 Update 方法

对于 update 方法，思路和 add 方法基本一样，但是如果要同时支持两个方法，需要考虑 update 方法会覆盖之前的 lazyAdd 的缓存任务。

首先提供一个递归调用的 update 方法，然后开放一个简化调用的 update 方法，如下：

private void update(int updateL, int updateR, int operateL, int operateR, int treeIndex, int updateNum) {// 全包直接可以更新if (updateL <= operateL && operateR <= updateR) {lazyUpdate[treeIndex] = updateNum;lazyUpdateFlag[treeIndex] = true;// 直接更新 sumsum[treeIndex] = updateNum * (operateR - operateL + 1);// 清空覆盖懒增加lazyAdd[treeIndex] = 0;return;}// 如果包不住，需要进行下发处理int mid = (operateL + operateR) >> 1;// 懒任务下发pushDownLazyTask(treeIndex, mid - operateL + 1, operateR - mid);if (updateL <= mid) {update(updateL, updateR, operateL, mid, treeIndex << 1, updateNum);}if (updateR > mid) {update(updateL, updateR, mid + 1, operateR, treeIndex << 1 | 1, updateNum);}sum[treeIndex] = sum[treeIndex << 1] + sum[treeIndex << 1 | 1];
}

这里提一下，我在第一次实现的时候，理所应当的思考就和 lazyAdd 一样，提供一个 lazyUpdate[] 数组来阻塞更新的下发就可以了，但是实际实现后是无法通过对数器的，因为无法判断是否有更新，我们无法简单的判断 lazyUpdate[index] != 0 就认定没有更新，有可能就是更新到了 0，所以需要一个标记更新的数组，最后我定义了 lazyUpdateFlag 来辅助判断是否有更新。

所以新增的结构为

private int[] lazyUpdate;
// 单独用一个数组标记是否进行了更新
private boolean[] lazyUpdateFlag;

对于懒任务下发就需要增加处理更新任务下发的逻辑

private void pushDownLazyTask(int index, int leftRange, int rightRange) {// 根据更新标记数组判断是否有懒更新，不然更新 0 的时候没法判断if (lazyUpdateFlag[index]) {int lazyUpdateNum = lazyUpdate[index];lazyUpdate[index] = 0;lazyUpdateFlag[index] = false;int left = index << 1;int right = index << 1 | 1;lazyAdd[left] = 0;lazyAdd[right] = 0;lazyUpdate[left] = lazyUpdateNum;lazyUpdateFlag[left] = true;lazyUpdate[right] = lazyUpdateNum;lazyUpdateFlag[right] = true;sum[left] = leftRange * lazyUpdateNum;sum[right] = rightRange * lazyUpdateNum;}// 这里最后还是会执行一遍懒添加的下发，因为存在先懒更新后再懒添加的情况，这块更新会清空覆盖懒添加，所以不会有先添加后更新的问题if (lazyAdd[index] != 0) {int lazyNum = lazyAdd[index];lazyAdd[index] = 0;lazyAdd[index << 1] += lazyNum;lazyAdd[index << 1 | 1] += lazyNum;sum[index << 1] += leftRange * lazyNum;sum[index << 1 | 1] += rightRange * lazyNum;}
}

这里对于懒更新，因为进行了下发，所以清除更新、添加，计算 sum 数组

最后对数器验证通过

public static void main(String[] args) {//对数器int testTimes = 5000;int addOrUpdateTimes = 5000;int maxAddOrUpdateNum = 5000;int testQueryTimes = 5000;Random random = new Random();//进行测试for (int i = 0; i < testTimes; i++) {int[] origin = RandomUtil.generateArray(30, 10);// System.out.println(Arrays.toString(origin));SegmentTree segmentTree = new SegmentTree(origin);SegmentTreeON segmentTreeON = new SegmentTreeON(origin);int originLength = origin.length;//每次测试进行添加更新操作次数for (int j = 0; j < addOrUpdateTimes; j++) {int num1 = random.nextInt(originLength) + 1;int num2 = random.nextInt(originLength) + 1;int L = Math.min(num1, num2);int R = Math.max(num1, num2);int num = random.nextInt(maxAddOrUpdateNum);if (random.nextInt(10) < 5) {segmentTree.add(L, R, num);segmentTreeON.add(L, R, num);} else {segmentTree.update(L, R, num);segmentTreeON.update(L, R, num);}}for (int k = 0; k < testQueryTimes; k++) {int num1 = random.nextInt(originLength) + 1;int num2 = random.nextInt(originLength) + 1;int L = Math.min(num1, num2);int R = Math.max(num1, num2);if (segmentTree.query(L, R) != segmentTreeON.query(L, R)) {System.out.println("L-R=" + L + "-" + R);System.out.println("segmentTree.query(L,R)=" + segmentTree.query(L, R));System.out.println("segmentTreeON.query(L,R)=" + segmentTreeON.query(L, R));System.out.println("error!!!!! testNum=" + k);return;}}System.out.println("right " + (i + 1));}
}