/**
* 线段树入门
* 问题:已知线段[2,5] [4,6] [0,7];求点2,4,7分别出现了多少次
* 以下代码建立的线段树用链表来保存,且树的叶子结点类似[i,i]
*
* 参考链接:http://hi.baidu.com/semluhiigubbqvq/item/be736a33a8864789f4e4ad18
* @author lijinnan
*/
public class SegmentTreeLearn {
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));
}
}
}
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);
}
//从根节点开始查找叶子结点[target, target],对经过的节点的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;
//匹配,出现次数加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);
}
}
}
分享到:
相关推荐
权值线段树和主席树入门PPT,权值线段树,顾名思义就是记录权值的线段树,普通的线段树直接以坐标为l,r建树,而权值线段树是以大小来建树,树上寸的信息是该权值的数量,而通过建树时二分从小到大的性质,可以用这...
一个线段树入门的讲义,写得很不错,比较适合初学者。
本着大家都能学习的精神,上传一些线段树的学习资料,本资料还是属于入门的,但是说的比较详细,大家配合着习题应该能较快掌握线段树
轻松学习线段树,通过我的PPT,你将会有信心更好的掌握线段树
线段树入门级总结 pdf版 原创编写,内含线段树基本操作与习题,方便OIer 与 Acmer
在[0,7]区间上建立一棵满二叉树:(为了和已知线段区别,用【】表示线段树中的线段) 【0,7】 / \ 【0,3】 【4,7】 / \ / \ 【0,1】 【2,3】 【4,5】 【6,7】 / \ / \ / \ / \ 【0,0】 【1,1】 【2,2】 【3,3...
线段树+入门+总结+Interval+Tree.rar
线段树,低级入门,易懂
NULL 博文链接:https://128kj.iteye.com/blog/1739064
NULL 博文链接:https://128kj.iteye.com/blog/1739733
线段树和树状数组acm中很重要的数据结构,本文深入浅出地讲解了线段树树状数组的原理和应用
线段树、树状数组算法入门 加 poj解题报告 pdf文档
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
NULL 博文链接:https://128kj.iteye.com/blog/1738772
线段覆盖0.成就 1.目录 C_Cpp STL 分治 动态规划 区间DP 哈希表 图论 最小生成树 最短路 奇思妙想 字符串 字符串匹配 常用技巧 并查集 排序 顺序统计量 搜索 BFS 二分搜索 回溯 数据结构 二叉树 树状数组 树(广义的...
文件包括以下子文件,每个文件里面包括了一定数量的ppt,doc,c++模板代码,希望对算法...8-线段树 9-树状数组 10-字典树 11-二分图 12-网络流 13-高精度 14-几何 15-自动机 16-DP_01背包 16-DP_树状dp 16-贪心 17-数论
《算法竞赛入门经典——训练指南》代码仓库 例题代码 限于篇幅,书上并没有给出所有例题的代码,... 增加线段树部分中两个经典问题的完整代码:快速序列操作I和快速序列操作II 2013-02-28 补全所有159道例题的代码