Daily Archives: January 14, 2015

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.         }
31.         addUtil(1, left, right);
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);
95.         tree.add(3, 6);
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. }

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.         }
31.         addUtil(1, left, right);
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);
95.         tree.add(3, 6);
96.         tree.print();
97.         System.out.println();
98.     }
99. }
101. class SegIntervalNode {
102.     int index;
103.     int left;
104.     int right;
105.     int cover;
106.     public SegIntervalNode() {
107.     }
108.     public SegIntervalNode(int index, int left, int right) {
109.         this.index = index;
110.         this.left = left;
111.         this.right = right;
112.     }
113. }