线段树

[zwkcoding]

线段树

定义

线段树是一种二叉搜索树

作用

在 O(log N) 的时间复杂度实现如：单点修改、区间查询（如：区间求和 ，区间最大值和最小值）

实现

二叉树，二分思想，递归实现

void build(int s, int t, int p)  {
  // 对 [s, t] 区间建树，当前根的编号为 p
  if ( s == t)  {
    d[p] = a[s];
    return ;
  }
  int m = (s + t) / 2;
  build(s , m, p * 2);
  build(m + 1, t, p * 2 +1);
  // 递归对左右区间建树
  d[p] = d[p * 2] + d[(p * 2) + 1];
}