Massive Algorithms: Segment Tree Java

http://www.sanfoundry.com/java-program-implement-segment-tree/
In computer science, a segment tree is a tree data structure for storing intervals, or segments. It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, its content cannot be modified once the structure is built. A similar data structure is the interval tree.
A segment tree for a set I of n intervals uses O(n log n) storage and can be built in O(n log n) time. Segment trees support searching for all the intervals that contain a query point in O(log n + k), k being the number of retrieved intervals or segments.

```
public class SegmentTree
```
```
{
```
```
    private int[] tree;
```
```
    private int maxsize;
```
```
    private int height;
```
```
    private  final int STARTINDEX = 0; 
```
```
    private  final int ENDINDEX;
```
```
    private  final int ROOT = 0;
```
```
    public SegmentTree(int size)
```
```
    {
```

        height = (int)(Math.ceil(Math.log(size) /  Math.log(2)));

        maxsize = 2 * (int) Math.pow(2, height) - 1;

```
        tree = new int[maxsize];
```
```
        ENDINDEX = size - 1; 
```
```
    }
```
```
    private int leftchild(int pos)
```
```
    {
```
```
        return 2 * pos + 1;
```
```
    }
```
```
    private int rightchild(int pos)
```
```
    {
```
```
        return 2 * pos + 2;
```
```
    }
```
```
    private int mid(int start, int end)
```
```
    {
```

        return (start + (end - start) / 2);

```
    }
```

    private int getSumUtil(int startIndex, int endIndex, int queryStart, int queryEnd, int current)

```
    {
```

        if (queryStart <= startIndex && queryEnd >= endIndex )

```
        {
```
```
            return tree[current];
```
```
        }
```

        if (endIndex < queryStart || startIndex > queryEnd)

```
        {
```
```
            return 0;
```
```
        }
```

        int mid = mid(startIndex, endIndex);

        return  getSumUtil(startIndex, mid, queryStart, queryEnd, leftchild(current))

                 + getSumUtil( mid + 1, endIndex, queryStart, queryEnd, rightchild(current));

```
    }
```

    public int getSum(int queryStart, int queryEnd)

```
    {
```

        if(queryStart < 0 || queryEnd > tree.length)

```
        {
```
```
            return -1;
```
```
        }
```

        return getSumUtil(STARTINDEX, ENDINDEX, queryStart, queryEnd, ROOT);

```
    }
```

    private int constructSegmentTreeUtil(int[] elements, int startIndex, int endIndex, int current)

```
    {
```
```
        if (startIndex == endIndex)
```
```
        {
```

            tree[current] = elements[startIndex];

```
            return tree[current]; 
```
```
        }
```

        int mid = mid(startIndex, endIndex);

        tree[current] = constructSegmentTreeUtil(elements, startIndex, mid, leftchild(current))

                           + constructSegmentTreeUtil(elements, mid + 1, endIndex, rightchild(current));

```
        return tree[current];
```
```
    }
```

    public void constructSegmentTree(int[] elements)

```
    {
```

        constructSegmentTreeUtil(elements, STARTINDEX, ENDINDEX, ROOT);

```
    }
```

    private void updateTreeUtil(int startIndex, int endIndex, int updatePos, int update, int current)

```
    {
```

        if ( updatePos < startIndex || updatePos > endIndex)

```
        {
```
```
            return;
```
```
        }
```

        tree[current] = tree[current] + update;

```
        if (startIndex != endIndex)
```
```
        {
```

            int mid = mid(startIndex, endIndex);

            updateTreeUtil(startIndex, mid, updatePos, update, leftchild(current));

            updateTreeUtil(mid+1, endIndex, updatePos, update, rightchild(current));

```
        }
```
```
    }
```

    public void update(int update, int updatePos, int[] elements)

```
    {
```

        int updatediff = update - elements[updatePos]  ;

```
        elements[updatePos] = update;
```

        updateTreeUtil(STARTINDEX, ENDINDEX, updatePos, updatediff, ROOT);

```
    }
```

    public static void main(String...arg)

```
    {
```

        int[] elements = {1,3,5,7,9,11};

        SegmentTree segmentTree = new SegmentTree(6);

        segmentTree.constructSegmentTree(elements);

        int num = segmentTree.getSum(1, 5);

```
 
```

        segmentTree.update(10, 5,elements);

```
        num = segmentTree.getSum(1, 5);
```
```
    }   
```
```
}
```

http://algs4.cs.princeton.edu/93intersection/IntervalST.java.html
Interval tree
http://en.wikipedia.org/wiki/Interval_tree

an interval tree is an ordered tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries, for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene. A similar data structure is the segment tree.

The trivial solution is to visit each interval and test whether it intersects the given point or interval, which requires Θ(n) time, where n is the number of intervals in the collection. Since a query may return all intervals, for example if the query is a large interval intersecting all intervals in the collection, this is asymptotically optimal; however, we can do better by considering output-sensitive algorithms, where the runtime is expressed in terms of m, the number of intervals produced by the query. Interval trees are dynamic, i.e., they allow insertion and deletion of intervals. They obtain a query time of O(log n) while the preprocessing time to construct the data structure is O(n log n) (but the space consumption is O(n)). If the endpoints of intervals are within a small integer range (e.g., in the range [1,...,O(n)]), faster data structures^[1] exist with preprocessing time O(n) and query time O(1+m) for reporting m intervals containing a given query point.

Also check http://codeforces.com/blog/entry/3327

Segment Tree Java

Labels

Popular Posts