# Segment tree1

By | January 14, 2015
Share the joy
•
•
•
•
•
•

Problem description:
Given a range [0, n]. Then given some of sections in [0, n], find the total sections in [0, n]
For example, given [0,8]. Then given section sets [2, 4], [3, 5], [6, 7].
The result should be [2, 5], [6, 7].
A brute force solution is to go over each section sets, find the overlapping part and return the result.
The following segment tree can achieve a O(logn) time query.
The following is my code:

1. package util;
2. public class SegmentTree {
3.     SegIntervalNode[] segNodes;
4.     public SegmentTree(int left, int right) {
5.         int diff = right – left; // diff is actually number of leaf.
6.         // Calculate the size of array according to diff
7.         int index = (int) Math.ceil(Math.log(diff) / Math.log(2));
8.         int space = (int) Math.pow(2, index) * 2;
9.         segNodes = new SegIntervalNode[space];
10.         constructSeg(1, left, right);
11.     }
12.     /*
13.      * Construct a SegNode, with range [left, right]. Put it to segNodes[index].
14.      */
15.     private void constructSeg(int index, int left, int right) {
16.         SegIntervalNode node = new SegIntervalNode(index, left, right);
17.         segNodes[index] = node;
18.         if (left + 1 < right) {
19.             int mid = (left + right) >> 1;
20.             constructSeg(index * 2, left, mid);
21.             constructSeg(index * 2 + 1, mid, right);
22.         }
23.     }
24.     /*
25.      * Add a segment [left, right] to segment tree
26.      */
27.     public void add(int left, int right) {
28.         if (left >= right) {
29.             return;
30.         }
32.     }
33.     private void addUtil(int index, int left, int right) {
34.         SegIntervalNode node = segNodes[index];
35.         if (left <= node.left && right >= node.right) {
36.             node.cover++;
37.             return;
38.         }
39.         int mid = (node.left + node.right) >> 1;
40.         if (left < mid) {
41.             addUtil(index * 2, left, right);
42.         }
43.         if (right > mid) {
44.             addUtil(index * 2 + 1, left, right);
45.         }
46.     }
47.     /*
48.      * Delete a segment [left, right] from segment tree
49.      */
50.     public void delete(int left, int right) {
51.         if (left >= right) {
52.             return;
53.         }
54.         deleteUtil(1, left, right);
55.     }
56.     private void deleteUtil(int index, int left, int right) {
57.         SegIntervalNode node = segNodes[index];
58.         if (left <= node.left && right >= node.right) {
59.             node.cover–;
60.             return;
61.         }
62.         int mid = (node.left + node.right) >> 1;
63.         if (left < mid) {
64.             deleteUtil(index * 2, left, right);
65.         }
66.         if (right > mid) {
67.             deleteUtil(index * 2 + 1, left, right);
68.         }
69.     }
70.     /*
71.      * Print all covered segments
72.      */
73.     public void print() {
74.         printUtil(1, segNodes[1].left, segNodes[1].right);
75.     }
76.     public void printUtil(int index, int left, int right) {
77.         SegIntervalNode node = segNodes[index];
78.         if (node.cover != 0) {
79.             System.out.println(“[” + left + “, ” + right + “]\t” + node.cover);
80.             return;
81.         }
82.         if (left + 1 >= right) {
83.             return;
84.         }
85.         int mid = (node.left + node.right) >> 1;
86.         if (left < mid) {
87.             printUtil(index * 2, left, mid);
88.         }
89.         if (right > mid) {
90.             printUtil(index * 2 + 1, mid, right);
91.         }
92.     }
93.     public static void main(String[] args) {
94.         SegmentTree tree = new SegmentTree(0, 8);
96.         tree.print();
97.         System.out.println();
98.     }
99. }
100. class SegIntervalNode {
101.     int index;
102.     int left;
103.     int right;
104.     int cover;
105.     public SegIntervalNode() {
106.     }
107.     public SegIntervalNode(int index, int left, int right) {
108.         this.index = index;
109.         this.left = left;
110.         this.right = right;
111.     }
112. }