線段樹模板

package segmentTree;public class SegmentTree {private class Segment { int left; int right; int count; Segment leftChild; Segment rightChild; } private Segment root; public SegmentTree (int left, int right) { root = new Segment(); build(root, left, right); } public void insert(int left, int right) { insert(root, left, right); } public int caculateExistingTimes(int target) { return caculateExistingTimes(root, target); } //從根節(jié)點(diǎn)開始查找葉子結(jié)點(diǎn)[target, target]，對經(jīng)過的節(jié)點(diǎn)的count求和 private int caculateExistingTimes(Segment root, int target) { int result = 0; while( root.left != root.right) { int rootMid = root.left + (root.right - root.left) / 2; result += root.count; if (target <= rootMid) { root = root.leftChild; } else if (target > rootMid) { root = root.rightChild; } } return result; } private void build(Segment root, int left, int right) { root.left = left; root.right = right; if (left != right) { int mid = left + (right - left) / 2; root.leftChild = new Segment(); root.rightChild = new Segment(); build(root.leftChild, left, mid); build(root.rightChild, mid + 1, right); } } private void insert(Segment root, int left, int right) { int rootLeft = root.left; int rootRight = root.right; int rootMid = rootLeft + (rootRight - rootLeft) / 2; //匹配，出現(xiàn)次數(shù)加1 if (left == rootLeft && right == rootRight) { root.count++; return; } if (right <= rootMid) { insert(root.leftChild, left, right); } else if (left > rootMid){ insert(root.rightChild, left, right); } else { insert(root.leftChild, left, rootMid); insert(root.rightChild, rootMid + 1, right); } } }
測試源碼 test.java

/** * 線段樹入門 * 問題：已知線段[2,5] [4,6] [0,7]；求點(diǎn)2,4,7分別出現(xiàn)了多少次 * 以下代碼建立的線段樹用鏈表來保存，且樹的葉子結(jié)點(diǎn)類似[i,i] */ package segmentTree; import segmentTree.SegmentTree;public class test {public static void main(String[] args) { SegmentTree tree = new SegmentTree(0, 7); int[][] segments = { {2, 5}, {4, 6}, {0, 7} }; int[] targets = {2, 4, 7}; for (int i = 0, len = segments.length; i < len; i++) { int[] segment = segments[i]; tree.insert(segment[0], segment[1]); } for(int target : targets) { System.out.println(target + ":" + tree.caculateExistingTimes(target)); } } }

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的java 数据结构源码--线段树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。