懒更新(lazy update) 上文留下一个问题没有解决，就是对一个区间更新。对一个元素的更新复杂度为O(N),N为数组长度,按上文方法对区间更新，则复杂度为L*O(N), L为区间长度。
另外，更新原数组元素，是从线段树中对应的叶子节点，一路向上更新到根节点。如果所要更新的区间有很多公共祖先节点，那么这些节点每次都需要被更新一次。如图中如果我们要更新数组中的2, 8, 6分别+5, +1, +9，可以看到图中公共节点如19会更新2次，37则有3次。
另外，在实际应用中，可能只是某些热点数据会频繁被读取，而大部分数据是在冷宫常年不见天日。有些更新没有必要立即落实到每一个节点，而可以在其被读取时再落实更新。
这就是懒更新的登场时刻。
基于数组的实现 既然需要将更新延后落实，那么就需要保存这些更新，所以需要一个与tree长度一致的lazy数组来保存对应节点没有落实的更新。代码如下。几个注意点：
进入queryCore时，首先需要检查有无当前节点index的更新，如果有，先执行更新，清空该更新，然后继续，其余与正常线段树query区别。 进入updateCore时，也是首先要检查有无当前节点index的更新，如果有，重复上面。 另外，当更新范围[left, right]完全覆盖当前节点代表区间[segLeft, segRight]时，要再次执行更新，但这次update参数是newVal。这是关键点所在，执行完更新，就不用继续递归调用了，因为孩子节点的更新被保存在了lazy[leftChild]和lazy[rightChild]。下次再调用query或者update时，如果执行到节点leftChild或rightChild，则会执行之前保存的更新。 class SegmentTree { private int[] tree; private int[] lazy; private int n; public SegmentTree(int n) { this.n = n; int len = (1 << (1 + (int)(Math.ceil(Math.log(n) / Math.log(2))))) - 1; tree = new int[len]; lazy = new int[len]; } public int query(int left, int right) { return queryCore(left, right, 0, n - 1, 0); } public void update(int left, int right, int newVal) { updateCore(left, right, 0, n - 1, 0, newVal); } private int queryCore(int left, int right, int segLeft, int segRight, int index) { if (lazy[index] != 0) { // Execute un-merged update. execute(index, lazy[index], segLeft, segRight); // Clear merged update. lazy[index] = 0; } if (left > segRight || right < segLeft) { return 0; } if (left <= segLeft && segRight <= right) { return tree[index]; } int mid = getMid(segLeft, segRight); return merge(queryCore(left, right, segLeft, mid, index * 2 + 1), queryCore(left, right, mid + 1, segRight, index * 2 + 2)); } private void updateCore(int left, int right, int segLeft, int segRight, int index, int newVal) { if (lazy[index] != 0) { execute(index, lazy[index], segLeft, segRight); lazy[index] = 0; } if (left > segRight || right < segLeft) { return; } if (left <= segLeft && segRight <= right) { // Execute update for newVal. execute(index, newVal, segLeft, segRight); return; } int mid = getMid(segLeft, segRight); updateCore(left, right, segLeft, mid, index * 2 + 1, newVal); updateCore(left, right, mid + 1, segRight, index * 2 + 2, newVal); tree[index] = merge(tree[index * 2 + 1], tree[index * 2 + 2]); } // Execute an update against tree[index] with interval [segLeft, segRight]. private void execute(int index, int update, int segLeft, int segRight) { // Apply the udpate. tree[index] = merge(tree[index], update); if (segLeft != segRight) { // Propagate the update to children. lazy[2 * index + 1] = merge(lazy[2 * index + 1], update); lazy[2 * index + 2] = merge(lazy[2 * index + 2], update); } } private int merge(int x, int y) { return Math.max(x, y); } private int getMid(int left, int right) { return left + (right - left) / 2; } } 基于树的实现 其实就是把上面的代码做一次翻译，不多赘述。
...