1. Segment Tree

1. Segment Tree

1.1. Description

Segment Tree is used to solve a problem in a certain range.

For example, query / update the max/min/sum/product of a certain range. Leetcode has several good example.

Leetcode 699 Falling Square
Leetcode 308 Range Sum Query 2D - Mutable This article will provide a standard way to write a segment tree in Java and provide a proof how it works and another small trick named lazy propagation.

Interface:

/**
 * @author jacka
 * @version 1.0 on 9/14/2017.
 */
public interface SegmentTree {

  /**
   * Update the value to <tt>val</tt> on index <tt>i</tt>.
   * @param i index to update
   * @param val value to set
   */
  void update(int i, int val);

  /**
   * To get the result of the range.
   *
   * @param rangeStart  range left boundary, inclusive
   * @param rangeEnd    range right boundary, inclusive
   * @return  result of the range, like sum, minimum value.
   */
  int get(int rangeStart, int rangeEnd);

}

1.2. Segment Tree Array Solution

Use range sum problem as an example.

1.2.1. Initialize segment tree array

The constructor looks like this

  // class fields
  private final int[] segmentTrees;
  private final int n;
  private final int[] values;

  public SegmentTreeSum(final int[] values) {
    n = values.length;
    this.values = values;
    final int height = (int) Math.ceil(Math.log(values.length) / Math.log(2));
    this.segmentTrees = new int[2 * (1 << height) + 1];
    if (n == 0) return;
    constructHelper(values, 0, values.length - 1, 0);
  }

Segment Tree is a full binary tree, which means every node has either 2 child nodes or 0.

Every value in values will be stored in the leaf.

So the question is with n leaves, how large the array we need to initialize to store the information in a segment tree.

The answer is given in the code already. Let's see the proof.

Height of the segment tree is (int) Math.ceil(Math.log(values.length) / Math.log(2))

数学归纳法 When values.length = 1, the conclusion is true.

Assuming values.length <= k the conclusion is true. When values.length = k + 1:

Since we always divide an range into halves, the segment tree will be complete except the last level. Let's say there are L$$$$l leaves in the left child node, L$$$$r in the right node. The difference of height of left and right trees will be 1.

We need prove height of (L$$$$l + L$$$$r) = Math.ceil(Math.log(L$$$$l + L$$$$r) / Math.log(2))

If the height of right child tree = the height of left child tree. Obviously, it's the same.
If the diff is 1, h(L$$$$l + L$$$$r) = Math.max(log(L$$$$l), log(L$$$$r)), where the base of log() in the equation is 2

Thus, it equals = Math.log(L$$$$max)/Math.log(2) + 1 = (Math.log(L$$$$max)+ Math.log(2))/ Math.log(2)
Total nodes is 2 * (1 << height) + 1

1.3. Segment Tree Node Solution

1.4. Segment Tree Lazy Propagation

Pitfall

During dealing with lazy[], whatever happened, the population of lazy[] array should happen.

Segment Tree