Segment tree - PEGWiki

The segment tree is a highly versatile data structure, based upon the divide-and-conquer paradigm, which can be thought of as a tree of intervals of an underlying array, constructed so that queries on ranges of the array as well as modifications to the array's elements may be efficiently performed.

The divide-and-conquer solution

The divide-and-conquer solution would be as follows:

• If the range contains one element, that element itself is trivially the minimum within that range.
• Otherwise, divide the range into two smaller ranges, each approximately half the size of the original, and find their respective minima. The minimum for the original range is then the smaller of the two minima of the sub-ranges

Problem from http://codeforces.com/blog/entry/3327

The problem that a segment tree can solve is the following. We are given an array of values a[0], a[1], ..., a[N - 1]. Assume without loss of generality that N = 2n; we can generally pad the computations accordingly. Also, consider some associative binary function f. Examples of f include sum, min, max, or gcd (as in the Timus problem). Segment trees allow for each of the following two operations onO(logN) time:

• compute f(a[i], a[i + 1], ..., a[j]) for i ≤ j; and
• update a[x] = v.

Java Program to Implement Segment Tree from http://www.sanfoundry.com/java-program-implement-segment-tree/

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);
    }
}

Also read http://www.sanfoundry.com/java-program-implement-segment-tree/
http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/
http://blog.mikemccandless.com/2013/12/fast-range-faceting-using-segment-trees.html
http://codeforces.com/blog/entry/3327
Read full article from Segment tree - PEGWiki