线段树

什么是线段树

按照我的简单理解，线段树其实是每个结点存放一个区间的值，使我们查询一个区间的时间复杂度从n变为logn。

当然时间复杂度的减少，空间也就会有相应的损失，当我们要通过线段树存储一个线性结构，空间的开销就会增大。比如我们存储的线性结构的大小正好是2的整数幂，那么我们所有的叶子节点都会是单个区间的值，这个叶子节点的数量就是n，我们知道对于一个满二叉树来说，叶子节点的数量就是上层所有节点的和，那么这时候我们需要开辟的空间就是2n。但是当我们存储的大小不是2的整数幂的时候，这时候单个区间节点就不全在叶子节点上，假设我们为了使线段树尽量满足满二叉树的结构，那么在倒数第二层的单个区间的值也需要两个左右孩子节点(虽然他们是空，但还是需要空间的)，那么这时候我们就需要开辟2n*2(4n)的空间。

线段树的实现

对于线段树的实现，我们需要使用递归调用。

具体思路如下:

不考虑动态规划的情况，我们需要将整个区间一分为二，这个 middleIndex 就是(left + right) / 2,然后我们再依次递归到最后的叶子节点，当我们需要划分的left = right的时候也就是区间为1的时候(即一个区间的值)我们返回，然后我们通过后序遍历的思想将两个左右子节点的值相融合赋值给父节点。

具体实现代码:

  private void buildSegmentTree(int treeIndex, int left, int right){
  if (left == right){
    tree[treeIndex] = data[left];
    return;
  }
  //获取左右孩子的节点索引
  int leftChildIndex = leftChild(treeIndex);
  int rightChildIndex = rightChild(treeIndex);

  //获取中间索引
  int middleIndex = left + (right - left) / 2;

  //int middleIndex = (left + right) / 2;
  //为了防止整型溢出

  buildSegmentTree(leftChildIndex, left, middleIndex);
  buildSegmentTree(rightChildIndex, middleIndex + 1, right);

  tree[treeIndex] = merger.merger(tree[leftChildIndex], tree[rightChildIndex]);
}

线段树的搜索

基本思路:

其实还是递归的思想，我们需要获取某个区间的值，即我们创建一个query方法，其中参数有treeIndex(遍历的根节点的index)，left(在什么区间查询的左边界index),right(在什么区间查询的右边界index),queryLeft(需要查询的左边界index),queryRight(需要查询的右边界的index)。

最根本的条件就是当我们所查询的左右边界值分别和我们需要查询的左右边界值相等，那么我们直接返回这个tree[treeIndex]。

我们使用递归转换为小问题的思路就是通过left right，queryLeft queryRight的关系，我们设置一个middleIndex(这个middleIndex也是根据left,right得来的)，我们通过queryLeft和middle比较，如果queryLeft比当前所查询区间的的middle要大的话，那么我们就去查询右子树，如果queryRight比middle要小的话我们就去查询左子树，因为我们查询的一个区间基本可能实现一个大区间的子集中，那么为了精确，我们就需要在大区间的左右孩子树中查找结果然后我们再将左右结果融合在一起然后返回。

代码实现:

  private E query(int treeIndex, int left, int right
    , int queryLeft, int queryRight){
  //当left == queryLeft && right == queryRight时就说明是我们需要查询的区间直接返回
  if (left == queryLeft && right == queryRight){
    return tree[treeIndex];
  }

  int middle = left + (right - left) / 2;

  int childLeftIndex = leftChild(treeIndex);
  int childRightIndex = rightChild(treeIndex);
  //缩小查询范围
  if (queryLeft >= middle + 1){
    return query(childRightIndex, middle + 1, right, queryLeft, queryRight);
  }
  if (queryRight <= middle){
    return query(childLeftIndex, left, middle, queryLeft, queryRight);
  }

  //我们查询的区间必定是某个大区间的左右孩子树查询结果的融合
  E leftResult = query(childLeftIndex, left, middle, queryLeft, queryRight);
  E rightResult = query(childRightIndex, middle + 1, right, queryLeft, queryRight);
  return merger.merger(leftResult, rightResult);
}

线段树查询的LeetCode题目

题目描述:

解题思路:

题目要求需要我们获得一个数组中某个区间段的值，并且这个sumRange函数会不断被调用，那么我们就可以使用线段树的查询操作(使merge融合改成相加就行了)

具体代码:

class NumArray{
  private SegmentTree<Integer> segmentTree;

  public NumArray(int[] nums) {
  Integer[] integers = new Integer[nums.length];
  if (nums.length > 0){
    for (int i = 0 ; i < nums.length ; i ++){
      integers[i] = nums[i];
    }
    //λ表达式，直接实现接口
    segmentTree = new SegmentTree<>(integers, (a, b) -> a + b);
    }
  }

  public int sumRange(int i, int j) {
    return segmentTree.query(i, j);
  }
}

线段树的修改

基本实现

这里我们主要实现对线段树的某个单区间的修改操作，对于单个线段树的修改操作势必会牵连到其父节点的修改，这里我们还是可以使用后序遍历的思想再更新完子节点之后将父节点更新。

相关代码:

  private void set(int treeIndex, int left, int right, int index, E e){
  //最根本条件就是我们查询的区间左右相等
  //这时候我们直接对该结点更新就行
  if (left == right){
    tree[treeIndex] = e;
    return;
  }
  //后面也是拿index和left，right比较
  //通过index和left，right的关系将问题变小
  int middleIndex = left + (right - left) / 2;

  int childLeftIndex = leftChild(treeIndex);
  int childRightIndex = rightChild(treeIndex);

  if (index <= middleIndex){
    set(childLeftIndex, left, middleIndex, index, e);
  }else if (index >= middleIndex + 1){
    set(childRightIndex, middleIndex, right, index, e);
  }
  //通过后序遍历的思想将父节点更新
  tree[treeIndex] = merger.merger(tree[childLeftIndex], tree[childRightIndex]);
}

相关的LeetCode题目

这里其实就是增加一个update方法，题目又增加了修改单个结点的值，那么我们将更新方法加入原来实现的代码中。

public void update(int i, int val) {
  segmentTree.update(i, val);
}