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.

  1. public class SegmentTree
  2. {
  3.     private int[] tree;
  4.     private int maxsize;
  5.     private int height;
  6.  
  7.     private  final int STARTINDEX = 0; 
  8.     private  final int ENDINDEX;
  9.     private  final int ROOT = 0;
  10.  
  11.     public SegmentTree(int size)
  12.     {
  13.         height = (int)(Math.ceil(Math.log(size) /  Math.log(2)));
  14.         maxsize = 2 * (int) Math.pow(2, height) - 1;
  15.         tree = new int[maxsize];
  16.         ENDINDEX = size - 1; 
  17.     }
  18.  
  19.     private int leftchild(int pos)
  20.     {
  21.         return 2 * pos + 1;
  22.     }
  23.  
  24.     private int rightchild(int pos)
  25.     {
  26.         return 2 * pos + 2;
  27.     }
  28.  
  29.     private int mid(int start, int end)
  30.     {
  31.         return (start + (end - start) / 2); 
  32.     }
  33.  
  34.     private int getSumUtil(int startIndex, int endIndex, int queryStart, int queryEnd, int current)
  35.     {
  36.         if (queryStart <= startIndex && queryEnd >= endIndex )
  37.         {
  38.             return tree[current];
  39.         }
  40.         if (endIndex < queryStart || startIndex > queryEnd)
  41.         {
  42.             return 0;
  43.         }
  44.         int mid = mid(startIndex, endIndex);
  45.         return  getSumUtil(startIndex, mid, queryStart, queryEnd, leftchild(current)) 
  46.                  + getSumUtil( mid + 1, endIndex, queryStart, queryEnd, rightchild(current));
  47.     }
  48.  
  49.     public int getSum(int queryStart, int queryEnd)
  50.     {
  51.         if(queryStart < 0 || queryEnd > tree.length)
  52.         {
  53.             return -1;
  54.         }
  55.         return getSumUtil(STARTINDEX, ENDINDEX, queryStart, queryEnd, ROOT);
  56.     }
  57.  
  58.     private int constructSegmentTreeUtil(int[] elements, int startIndex, int endIndex, int current)
  59.     {
  60.         if (startIndex == endIndex)
  61.         {
  62.             tree[current] = elements[startIndex];
  63.             return tree[current];	
  64.         }
  65.         int mid = mid(startIndex, endIndex);
  66.         tree[current] = constructSegmentTreeUtil(elements, startIndex, mid, leftchild(current))
  67.                            + constructSegmentTreeUtil(elements, mid + 1, endIndex, rightchild(current));
  68.         return tree[current];
  69.     }
  70.  
  71.     public void constructSegmentTree(int[] elements)
  72.     {
  73.         constructSegmentTreeUtil(elements, STARTINDEX, ENDINDEX, ROOT);	
  74.     }
  75.  
  76.     private void updateTreeUtil(int startIndex, int endIndex, int updatePos, int update, int current)
  77.     {
  78.         if ( updatePos < startIndex || updatePos > endIndex)
  79.         {
  80.             return;
  81.         }
  82.         tree[current] = tree[current] + update;
  83.         if (startIndex != endIndex)
  84.         {
  85.             int mid = mid(startIndex, endIndex);
  86.             updateTreeUtil(startIndex, mid, updatePos, update, leftchild(current));
  87.             updateTreeUtil(mid+1, endIndex, updatePos, update, rightchild(current));
  88.         }
  89.     }
  90.  
  91.     public void update(int update, int updatePos, int[] elements)
  92.     {
  93.         int updatediff = update - elements[updatePos]  ;
  94.         elements[updatePos] = update;
  95.         updateTreeUtil(STARTINDEX, ENDINDEX, updatePos, updatediff, ROOT);
  96.     }
  97.  
  98.     public static void main(String...arg)
  99.     {
  100.         int[] elements = {1,3,5,7,9,11};
  101.         SegmentTree segmentTree = new SegmentTree(6);
  102.         segmentTree.constructSegmentTree(elements);
  103.         int num = segmentTree.getSum(1, 5);
  104.  
  105.         System.out.println("the num is " + num);
  106.         segmentTree.update(10, 5,elements);
  107.         num = segmentTree.getSum(1, 5);
  108.         System.out.println("the num is " + num);	
  109.     }  	
  110. }


$javac SegmentTree.java
$java SegmentTree
the sum is 35
the sum is 34

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.