Java数据结构之线段树的原理与实现

@Data
public static class Node {
   //区间起始下标
   private int start;
   //区间结尾下标
   private int end;
   //当前区间和值
   private int value;
   private Node left;
   private Node right;
   Node(int start, int end, int value) {
       this.start = start;
       this.end = end;
       this.value = value;
  }
}

//head 指向线段树root节点的指针，使得root节点与其余节点操作保持一致
   Node head;
   int size;
   List<Integer> nums;

   //前缀和数组，便于构建线段树时候计算区间值，用于初次构建辅助
   List<Integer> prefixSum ;
   public void init(List<Integer> nums) {
       //初始化一个头节点，便于操作
       this.head = new Node(-1, -1, -1);
       this.nums = nums;
    //初始化前缀和数组
       prefixSum = new ArrayList<>(nums.size());
       prefixSum.add(0);
       for (int i = 0; i < nums.size() ; i++) {
           prefixSum.add(prefixSum.get(prefixSum.size() - 1) + nums.get(i));
      }
    //构建线段树
       this.build(1, nums.size());
       size = nums.size();
  }

   //构建线段树
   public void build(int start, int end) {
      Node root = new Node(start, end, prefixSum.get(end) - prefixSum.get(start - 1));
     //将头节点右子树指向root
      head.right = root;
     //从root开始构建线段树
      this.madeChild(root, start, end);
  }
private void madeChild(Node node, int start, int end) {
       if (start >= end) {
           return;
      }
       //分个左右子树，左子树取start～mid，右子树取mid+1～end
       int mid = start + ((end - start) >> 1);
       if (start <= mid) {
           Node left = new Node(start, mid, prefixSum.get(mid) - prefixSum.get(start - 1));
           node.left = left;
           madeChild(left, start, mid);
      }
       if (mid + 1 <= end) {
           Node right = new Node(mid + 1, end, prefixSum.get(end) - prefixSum.get(mid));
           node.right = right;
           madeChild(right, mid + 1, end);
      }
  }

//求解区间和
   public int findSectionSum(int start, int end) {
       //深度遍历线段树，找到对应区间
       if (start < 1 || end > size || start > end) {
           return -1;
      }
       return dfsFindSectionSum(head.right, start, end);
  }    
/**
    * 深度遍历线段树结构，分为三种情况
    * 1.区间在当前节点的左子树中
    * 2.区间在当前节点的右子树中
    * 3.左子树中一部分，右子树中一部分
    * @param node
    * @param start
    * @param end
    * @return
    */
   private int dfsFindSectionSum(Node node, int start, int end) {
       if (node.start == start && node.end == end) {
           //找到区间
           return node.value;
      }
       if (this.isContain(node.left.start, node.left.end, start, end)) {
           //在左子树中
           return this.dfsFindSectionSum(node.left, start, end);
      }
       if (this.isContain(node.right.start, node.right.end, start, end)) {
           //包含在右子树中
           return this.dfsFindSectionSum(node.right, start, end);
      }
       //左边一部分，右边一部分
       return this.dfsFindSectionSum(node.left, start, node.left.end) + this.dfsFindSectionSum(node.right, node.right.start, end);
  }
   /**
    * 判断区间[start2, end2]是否包含在[start1, end1]中
    * @param start1
    * @param end1
    * @param start2
    * @param end2
    * @return
    */
   private boolean isContain(int start1, int end1, int start2, int end2){
       return start2 >= start1 && end2 <= end1;
  }

//更新线段树，将index位置的值更新为value，需要更新沿路的值
   public void update(int index, int value) {
       Node root = head.right;
       while (null != root) {
           if (index >= root.start && index <= root.end) {
               root.value += value - nums.get(index - 1);
          }
           int mid = root.start + ((root.end - root.start) >> 1);
           if (index <= mid) {
               root = root.left;
               continue;
          }
           root = root.right;
      }
       nums.set(index - 1, value);
  }