# Segment Tree Build

## Question

The structure of Segment Tree is a binary tree which each node has two attributes `start` and `end` denote an segment / interval.

`start` and `end` are both integers, they should be assigned in following rules:

* The root's start and end is given by `build` method.
* The left child of node A has `start=A.left, end=(A.left + A.right) / 2`.
* The right child of node A has `start=(A.left + A.right) / 2 + 1, end=A.right`.

  if start equals to end, there will be no children for this node.

Implement a `build` method with two parameters start and end, so that we can create a corresponding segment tree with every node has the correct start and end value, return the root of this segment tree.

### Clarification

Segment Tree (a.k.a Interval Tree) is an advanced data structure which can support queries like:

* which of these intervals contain a given point
* which of these points are in a given interval

See wiki:

[Segment Tree](https://en.wikipedia.org/wiki/Segment_tree)

[Interval Tree](https://en.wikipedia.org/wiki/Interval_tree)

**Example**\
Given start=0, end=3. The segment tree will be:

```
               [0,  3]
             /        \
      [0,  1]           [2, 3]
      /     \           /     \
   [0, 0]  [1, 1]     [2, 2]  [3, 3]
```

Given start=1, end=6. The segment tree will be:

```
               [1,  6]
             /        \
      [1,  3]           [4,  6]
      /     \           /     \
   [1, 2]  [3,3]     [4, 5]   [6,6]
   /    \           /     \
[1,1]   [2,2]     [4,4]   [5,5]
```

## Analysis

求出中间值，再分别对left，right进行build，递归调用build，生成子树。

## Solution

```java
/**
 * Definition of SegmentTreeNode:
 * public class SegmentTreeNode {
 *     public int start, end;
 *     public SegmentTreeNode left, right;
 *     public SegmentTreeNode(int start, int end) {
 *         this.start = start, this.end = end;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     *@param start, end: Denote an segment / interval
     *@return: The root of Segment Tree
     */
    public SegmentTreeNode build(int start, int end) {
        if(start > end) {  // check core case
            return null;
        }

        SegmentTreeNode root = new SegmentTreeNode(start, end);

        if(start != end) {
            int mid = (start + end) / 2;
            root.left = build(start, mid);
            root.right = build(mid + 1, end);
        }
        return root;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/segment_tree/segment_tree_build.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.