线段树 05 在线段树中更新单个元素

在线段树中更新单个元素

• 在线段树中更新一个元素的过程分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]);
}