线段树(区间树)
麦兜 / 2020-03-16 / 数据结构 / 阅读量 202

什么是线段树

线段树也称区间树,更多的用于查询数据区间的值。

线段树和二分搜索树相似也是二叉树,但具体的现实是不一样的。

线段树对于需要频繁动态更新和查询的数据是比普通算法是更有利。(当然lazy我暂时留个坑有空再填)

时间复杂度查询修改
普通算法O(1)O(n)
线段树O(logn)O(logn)

下方图以数值区间求和为例,每个节点的数值的和都平坦到子节点上。所以查询的时候只需要访问到区间节点就好了,而不需要每个值都访问。

例如:数组A[0,1,2,3,4,5,6,7] 查询0到3的区间值,只需要访问到根节点的右子节点就可以拿到区间值。

当然线段树不只是可以拿来做区间求和也可以拿来比较最大值最小值等操作。

线段树的构建样例图:
线段树.png

用数组实现线段树

  • 用数组实现线段树需要用把它当作满二叉树存储。
  • 对于满二叉树h层一共有2^h-1个节点。
  • 最后一层(h-1) 有2^(h-1)个节点。
  • 如果n=2^k 只需要2n的空间,但是最坏的情况为n=2^k+1 所以需要开4n的空间 (右边高度比左边高度多1层)

例子:计算区间值的和

普通数组.png

构建算法大概为从中间分开 为左右子节点。(同时计算或比较等操作)

左子节点:父节点下标*2+1

右子节点:父节点下标*2+2

线段树构建.png

构建线段树

  static int data[] = {0, 1, 2, 3, 4}; // 原数据
  static int Tree[] = new int[data.length * 4]; // 线段树

  public static void main(String[] args) {
      
    build(0, 0, data.length - 1);
    System.out.println(Arrays.toString(Tree));
  }

  private static void build(int NodeIndex, int l, int r) {
    // 当区间只有一个
    if (l == r) {
      Tree[NodeIndex] = data[l];
      return;
    }
    // 计算左右子节点的索引
    int LeftIndex = 2 * NodeIndex + 1;
    int RiIndex = 2 * NodeIndex + 2;

    //把数值区间二分
    int mid = l + (r - l) / 2;
    build(LeftIndex, l, mid);
    build(RiIndex, mid + 1, r);

    // 当前节点等于子节点的和。
    Tree[NodeIndex] =Tree[LeftIndex]+Tree[RiIndex] ;
  }
    
    
 输出结果:[10, 3, 7, 1, 2, 3, 4, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

区间查询

线段树查询.png

 private static int query(int NodeIndex,int l,int r,int start, int end) {

      if((l==start)&&(r==end)) {
          return Tree[NodeIndex];
      }

      // 计算左右子节点的索引
      int LeftIndex = 2 * NodeIndex + 1;
      int RiIndex = 2 * NodeIndex + 2;

      int mid = l + (r - l) / 2;
       //如果要查询的起始位置在右边范围内只需要去右边查询就好了,
      // 同理如果区间结束位置只在左边范围内就只需要去左边查询。
      if(start>=mid+1)
      {
          return query(RiIndex,mid+1,r,start,end);
      }
      else if(end<=mid)
      {
          return query(LeftIndex,l,mid,start,end);
      }
        // 当左右子树都存在区间时,查询的区间值也要分开去子树查询
      return query(LeftIndex,l,mid,start,mid)+query(RiIndex,mid+1,r,mid+1,end);
  }

更新数据


/*
* index 需要更新的索引位置
* value 需要更新的值
* NodeIndex 当前节点
* l 区间起始
* r 区间结束
*/
private static void update(int index,int value,int NodeIndex,int l,int r) {

        if(l==r)
        {
            //更新原数据
            data[index]=value;
            //更新树节点
            Tree[NodeIndex]=value;
        }
        else {

            int mid = l + (r - l) / 2;
            int LeftIndex = 2 * NodeIndex + 1;
            int RiIndex = 2 * NodeIndex + 2;

            //如果节点属于在右边范围就去右边更新子节点,属于左边就去左边更新。
            if(index>=mid+1)
            {
                update(index,value,RiIndex,mid+1,r);
            }
            else {
                update(index,value,LeftIndex,l,mid);
            }
            //维护更新父节点
            Tree[NodeIndex]=Tree[LeftIndex]+Tree[RiIndex];
        }
  }

线段树Lazy

如果用普通方法去频繁更新值的话会造成 时间复杂度变成O(N logN)。其实每次更新没有必要去更新到子节点 ,只需要更新到要查询的区间即可(偷懒),其余存放在另一个地方等查询超出未更新的结点再去更新。这样时间复杂度是O(logn)的。(暂时没学留个坑到时再填。)

1 + 1 =
快来做第一个评论的人吧~