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.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

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 & technical discussions at Telegram SanfoundryClasses.