Java Program to Implement Segment Tree

This Java program is to 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.

Here is the source code of the Java program to Implement Segment Tree. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.

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);
 
        System.out.println("the num is " + num);
        segmentTree.update(10, 5,elements);
        num = segmentTree.getSum(1, 5);
        System.out.println("the num is " + num);	
    }  	
}
$javac SegmentTree.java
$java SegmentTree
the sum is 35
the sum is 34

Related posts:

Default Password Encoder in Spring Security 5
Java Program to Implement ConcurrentSkipListMap API
Java Program to Check whether Graph is a Bipartite using BFS
Serialization và Deserialization trong java
Spring Cloud Connectors and Heroku
The Dining Philosophers Problem in Java
Spring Data MongoDB – Indexes, Annotations and Converters
Java Web Services – JAX-WS – SOAP
Java Program to Implement Sorted Singly Linked List
Java Program to Implement JobStateReasons API
Spring Boot - Flyway Database
Java NIO2 Path API
Java Program to Check Whether Topological Sorting can be Performed in a Graph
Java Program to Implement Regular Falsi Algorithm
Apache Commons Collections Bag
Java Program to Implement SimpeBindings API
Disable DNS caching
Spring Boot Gradle Plugin
Spring Boot - Tracing Micro Service Logs
The Difference Between map() and flatMap()
Working With Maps Using Streams
Custom JUnit 4 Test Runners
Java Program to Implement vector
Deploy a Spring Boot App to Azure
Java Program to Implement Heap
Java Program to Generate All Possible Combinations Out of a, b, c, d, e
Java Program to Find the Shortest Path from Source Vertex to All Other Vertices in Linear Time
Xử lý ngoại lệ đối với trường hợp ghi đè phương thức trong java
Introduction to Spring Cloud Netflix – Eureka
Java Program to Generate Random Partition out of a Given Set of Numbers or Characters
Get and Post Lists of Objects with RestTemplate
Java Program to Implement the Binary Counting Method to Generate Subsets of a Set