线段树-入门 - 代码物语-Let code talk - ITeye技术网站

线段树-入门 - 代码物语-Let code talk - ITeye技术网站

 * 问题：已知线段[2,5] [4,6] [0,7]；求点2,4,7分别出现了多少次 

 * 以下代码建立的线段树用链表来保存，且树的叶子结点类似[i,i] 

1. public class SegmentTreeLearn {  
2.   
3.     public static void main(String[] args) {  
4.         SegmentTree tree = new SegmentTree(0, 7);  
5.         int[][] segments = {  
6.                 {2, 5},   
7.                 {4, 6},   
8.                 {0, 7}  
9.         };  
10.         int[] targets = {2, 4, 7};  
11.         for (int i = 0, len = segments.length; i < len; i++) {  
12.             int[] segment = segments[i];  
13.             tree.insert(segment[0], segment[1]);  
14.         }  
15.         for(int target : targets) {  
16.             System.out.println(target + ":" + tree.caculateExistingTimes(target));  
17.         }  
18.     }  
19.       
20.   
21.   
22. }  
23.   
24. class SegmentTree {  
25.   
26.     //递归定义的，因此很多操作都是递归实现  
27.     private class Segment {  
28.         int left;  
29.         int right;  
30.         int count;  
31.         Segment leftChild;  
32.         Segment rightChild;  
33.     }  
34.       
35.     private Segment root;  
36.       
37.     public SegmentTree (int left, int right) {  
38.         root = new Segment();  
39.         build(root, left, right);  
40.     }  
41.       
42.     public void insert(int left, int right) {  
43.         insert(root, left, right);  
44.     }  
45.       
46.     public int caculateExistingTimes(int target) {  
47.         return caculateExistingTimes(root, target);  
48.     }  
49.       
50.     //从根节点开始查找叶子结点[target, target]，对经过的节点的count求和  
51.     private int caculateExistingTimes(Segment root, int target) {  
52.         int result = 0;  
53.         while( root.left != root.right) {  
54.             int rootMid = root.left + (root.right - root.left) / 2;  
55.             result += root.count;  
56.             if (target <= rootMid) {  
57.                 root = root.leftChild;  
58.             } else if (target > rootMid) {  
59.                 root = root.rightChild;  
60.             }  
61.         }  
62.         return result;  
63.     }  
64.      
65.     private void build(Segment root, int left, int right) {  
66.         root.left = left;  
67.         root.right = right;  
68.         if (left != right) {  
69.             int mid = left + (right - left) / 2;  
70.             root.leftChild = new Segment();  
71.             root.rightChild = new Segment();  
72.             build(root.leftChild, left, mid);  
73.             build(root.rightChild, mid + 1, right);  
74.         }  
75.     }  
76.       
77.     private void insert(Segment root, int left, int right) {  
78.           
79.         int rootLeft = root.left;  
80.         int rootRight = root.right;  
81.         int rootMid = rootLeft + (rootRight - rootLeft) / 2;  
82.           
83.         //匹配，出现次数加1  
84.         if (left == rootLeft && right == rootRight) {  
85.             root.count++;  
86.             return;  
87.         }  
88.           
89.         if (right <= rootMid) {  
90.             insert(root.leftChild, left, right);  
91.         } else if (left > rootMid){  
92.             insert(root.rightChild, left, right);  
93.         } else {  
94.             insert(root.leftChild, left, rootMid);  
95.             insert(root.rightChild, rootMid + 1, right);  
96.         }  
97.     }  
98.       
99. }  

Read full article from 线段树-入门 - 代码物语-Let code talk - ITeye技术网站