背景
在线段树的通常用法中,线段树的节点是有2种不同的意义的,
一种是离散型的:一个节点虽然描述的是一个区间[3, 9],但是实际上这样一个区间是{3, 4, 5, 6, 7, 8, 9}这样的意义。
而另一种就是连续型的:一个节点如果描述的是一个区间[3, 9],它就确确实实描述的是在数轴上从3这个标记到9这个标记的这一段。
这两种不同的意义有什么区别呢?
有这样的几个区别:
1.叶子节点:在离散型中,叶子节点是[i, i],而连续性中是[i, i + 1];
2.分解区间:在离散型中,一段区间是分解成为[l, m], [m + 1, r],而在连续型中,是......
阅读全文