# Segment tree2

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

Evolved from segment tree1, this segment tree can find not only the segments, but also individual points. The code is quite similar to segment tree1, please refer here link.
Below is my code:

1. package util;
2. public class IntervalTree {
3.     SegIntervalNode[] segNodes;
4.     public IntervalTree(int left, int right) {
5.         int diff = right – left + 1; // 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 < right) {
19.             int mid = (left + right) >> 1;
20.             constructSeg(index * 2, left, mid);
21.             constructSeg(index * 2 + 1, mid + 1, 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 >= 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 + 1, right);
91.         }
92.     }
93.     public static void main(String[] args) {
94.         IntervalTree tree = new IntervalTree(0, 7);
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. }