在线段树中更新单个元素
- 在线段树中更新一个元素的过程分2步：
- 在data中更新；
- 由于data的更新导致在tree上也要更新；
// 将index位置的值，更新为e
public void set(int index, E e){
if(index < 0 || index >= data.length)
throw new IllegalArgumentException("Index is illegal");
data[index] = e;
set(0, 0, data.length - 1, index, e);
}
- 在tree中做协变的更新是个递归问题：在treeIndex为根的线段树中更新index的值为e；
- 规模更小的同一个问题是：在treeIndex的左右子树中更新index的值为e；
- 当index <= mid时：在treeIndex的左子树中更新index的值为e；
- 当index >= mid + 1时：在treeIndex的右子树中更新index的值为e；
- treeIndex的左右子树都更新完成之后，重新合并treeIndex的左右孩子的值，赋予tree[treeIndex]；
- 不能再缩小的基本问题是：treeIndex已经是叶子节点了，其只代表了data中的一个元素，即 l == r，就在tree中把tree[treeIndex]更新为e；
// 在以treeIndex为根的线段树中更新index的值为e
private void set(int treeIndex, int l, int r, int index, E e){
if(l == r){
tree[treeIndex] = e;
return;
}
int mid = l + (r - l) / 2;
// treeIndex的节点分为[l...mid]和[mid+1...r]两部分
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
if(index >= mid + 1)
set(rightTreeIndex, mid + 1, r, index, e);
else // index <= mid
set(leftTreeIndex, l, mid, index, e);
tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
}
