《线段树/树状数组》，您将学到线段树能解决什么问题以及运用场景，如何快速实现整体批量更新修改、批量查询，线段树是不错的选择。

一、介绍

线段树也称树状数组，主要解决什么问题呢？

线段树是一种支持范围整体修改和范围整体查询的数据结构

方法一：通过遍历的方式修改和查询，时间复杂度O(N)

方法二：通过线段树实现，时间复杂度O(logN)

如果让你提供一种服务，范围内整体更新或范围内整体查询，而且访问量比较大，你会怎么设计？从时间复杂度上看，当然选O(logN)了，这时候线段树就能帮你解决这种问题了。

如下说明线段树需要实现的功能：

给定一个数组arr，用户希望你实现如下三个方法

• void add(int L, int R, int V) : 让数组arr[L…R]上每个数都加上V
• void update(int L, int R, int V) : 让数组arr[L…R]上每个数都变成V
• int sum(int L, int R) : 让返回arr[L…R]这个范围整体的累加和

怎么让这三个方法，时间复杂度都是O(logN)

二、分析

线段树的实现有非递归版本实现，但有些麻烦！！！

线段树的递归方法实现，不用担心栈会溢出情况，因为不可能那么大

假设有 N = 2^26 规模的数据，这已经很大了，那么logN = 64，也就64次搞定

把数组转换成一个树状结构，规定数组下标从1开始，容易理解，正常数组下标是从0开始的

数组转换成二叉树结构：

申请一个数组空间，里边放格子，0位置不用，再把数组进行转换成二叉树结构：

新数组的任何格子节点都能找到它的父节点，公式为：i/2

i格子信息：

• 父节点：i/2
• 左孩子：2*i
• 右孩子：2*i + 1

有了这个公式，就知道任何格子在哪个位置，也知道当前格子的父节点在哪，左孩子在哪，右孩子在哪

当一个任务到来时，往下发的过程，卡主一个左边界，卡主一个右边界，涉及到懒更新停止下发，只要不全包就下发

懒更新：当前格子任务的起始和结束位置在下发任务的起始和结束范围内，就是任务被包住了，停止下发给下边的格子，用一个懒格子记录起来

三、实现

public static class SegmentTree {
  // arr[]为原序列的信息从0开始，但在arr里是从1开始的
  // sum[]模拟线段树维护区间和
  // lazy[]为累加和懒惰标记
  // change[]为更新的值
  // update[]为更新慵懒标记
  private int MAXN;
  private int[] arr;
  private int[] sum;
  private int[] lazy;
  private int[] change;
  private boolean[] update;

  public SegmentTree(int[] origin) {
    MAXN = origin.length + 1;
    arr = new int[MAXN]; // arr[0] 不用 从1开始使用
    for (int i = 1; i < MAXN; i++) {
      arr[i] = origin[i - 1];
    }
    sum = new int[MAXN << 2];
    lazy = new int[MAXN << 2];
    change = new int[MAXN << 2];
    update = new boolean[MAXN << 2];
  }

  private void pushUp(int rt) {
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
  }

  // 之前的，所有懒增加，和懒更新，从父范围，发给左右两个子范围
  // 分发策略是什么
  // ln表示左子树元素结点个数，rn表示右子树结点个数
  private void pushDown(int rt, int ln, int rn) {
    if (update[rt]) {
      update[rt << 1] = true;
      update[rt << 1 | 1] = true;
      change[rt << 1] = change[rt];
      change[rt << 1 | 1] = change[rt];
      lazy[rt << 1] = 0;
      lazy[rt << 1 | 1] = 0;
      sum[rt << 1] = change[rt] * ln;
      sum[rt << 1 | 1] = change[rt] * rn;
      update[rt] = false;
    }
    if (lazy[rt] != 0) {
      lazy[rt << 1] += lazy[rt];
      sum[rt << 1] += lazy[rt] * ln;
      lazy[rt << 1 | 1] += lazy[rt];
      sum[rt << 1 | 1] += lazy[rt] * rn;
      lazy[rt] = 0;
    }
  }

  // 在初始化阶段，先把sum数组，填好
  // 在arr[l~r]范围上，去build，1~N，
  // rt : 这个范围在sum中的下标
  public void build(int l, int r, int rt) {
    if (l == r) {
      sum[rt] = arr[l];
      return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    pushUp(rt);
  }


  // L~R  所有的值变成C
  // l~r  rt
  public void update(int L, int R, int C, int l, int r, int rt) {
    if (L <= l && r <= R) {
      update[rt] = true;
      change[rt] = C;
      sum[rt] = C * (r - l + 1);
      lazy[rt] = 0;
      return;
    }
    // 当前任务躲不掉，无法懒更新，要往下发
    int mid = (l + r) >> 1;
    pushDown(rt, mid - l + 1, r - mid);
    if (L <= mid) {
      update(L, R, C, l, mid, rt << 1);
    }
    if (R > mid) {
      update(L, R, C, mid + 1, r, rt << 1 | 1);
    }
    pushUp(rt);
  }

  // L~R, C 任务！
  // rt，l~r
  public void add(int L, int R, int C, int l, int r, int rt) {
    // 任务如果把此时的范围全包了！
    if (L <= l && r <= R) {
      sum[rt] += C * (r - l + 1);
      lazy[rt] += C;
      return;
    }
    // 任务没有把你全包！
    // l  r  mid = (l+r)/2
    int mid = (l + r) >> 1;
    pushDown(rt, mid - l + 1, r - mid);
    // L~R
    if (L <= mid) {
      add(L, R, C, l, mid, rt << 1);
    }
    if (R > mid) {
      add(L, R, C, mid + 1, r, rt << 1 | 1);
    }
    pushUp(rt);
  }

  // 1~6 累加和是多少？ 1~8 rt
  public long query(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R) {
      return sum[rt];
    }
    int mid = (l + r) >> 1;
    pushDown(rt, mid - l + 1, r - mid);
    long ans = 0;
    if (L <= mid) {
      ans += query(L, R, l, mid, rt << 1);
    }
    if (R > mid) {
      ans += query(L, R, mid + 1, r, rt << 1 | 1);
    }
    return ans;
  }

}