Fenwick 树中的范围查询
Range querying in Fenwick Tree
我正在尝试解决这个涉及查询分域树的问题。
问题陈述如下：
这是一个来自 Hackerrank 竞赛的问题：link
给你一棵树，其中每个节点都标记为 1、2、...、n。这棵树中有多少相似对(S)？
一对 (A,B) 是相似的一对当且仅当
- 节点A是节点B的祖先
- abs(A - B) <= T.
输入格式：
输入的第一行包含两个整数 n 和 T。接下来是 n-1 行，每行包含两个整数 si 和 ei，其中节点 si 是节点 ei 的父节点。
输出格式：
输出一个整数，表示树中相似对的数量
限制条件：
1 <= n <= 100000
0 <= T <= n
1 <= si, ei <= n.
也保证没有环路，但树不一定是二叉树
示例输入：
5 2
3 2
3 1
1 4
1 5
示例输出：
4
说明：
相似的对是：(3, 2) (3, 1) (3, 4) (3, 5)
我的算法：
我会在DFS中遍历树，同时维护一个HashSet S用于查询。在进入节点时，我将向 S 添加一个节点 x，而在离开时，我会将其从集合中移除。
现在为了找到特定叶节点的答案，我需要找出 Set 中遵循 x-T <= y <= x+T 的节点数，其中 'y' 是祖先，x-T 和 x +T 是范围内的节点。
我了解 Fenwick 树的概念，但我无法设计在树中存储什么以便进行范围查询，或者具体如何进行范围查询。我了解检索总和时它是如何工作的，但是 给定一个范围 [left, right] 我如何找到存储在 tree
中的范围内的元素数
我在普林斯顿算法中找到了查询芬威克树的示例。你可以在这里找到它：
http://algs4.cs.princeton.edu/99misc/FenwickTree.java.html
希望对您的上下文有所帮助。
注意标签的范围最多为10^5，所以可以将标签存储在分域树中。用1表示存在一个节点，否则为0。那么sum表示节点总数。
假设我们有 Fenwick 树 T，方法
add(pos, val), add val 在位置 pos, O(lgn)sum(pos)，得到位置1到pos的和，O(lgn)
while dfs，插入节点x，执行T.add(x, 1)，删除节点x，执行T.add(x, -1)，查询节点[=17] =], 即 T.sum(x+k) - T.sum(x-k-1).
有关详细信息，请参阅 code。
我正在尝试解决这个涉及查询分域树的问题。 问题陈述如下：
这是一个来自 Hackerrank 竞赛的问题：link
给你一棵树，其中每个节点都标记为 1、2、...、n。这棵树中有多少相似对(S)？
一对 (A,B) 是相似的一对当且仅当
- 节点A是节点B的祖先
- abs(A - B) <= T.
输入格式： 输入的第一行包含两个整数 n 和 T。接下来是 n-1 行，每行包含两个整数 si 和 ei，其中节点 si 是节点 ei 的父节点。
输出格式： 输出一个整数，表示树中相似对的数量
限制条件：
1 <= n <= 100000
0 <= T <= n
1 <= si, ei <= n.
也保证没有环路，但树不一定是二叉树
示例输入：
5 2
3 2
3 1
1 4
1 5
示例输出：
4
说明： 相似的对是：(3, 2) (3, 1) (3, 4) (3, 5)
我的算法： 我会在DFS中遍历树，同时维护一个HashSet S用于查询。在进入节点时，我将向 S 添加一个节点 x，而在离开时，我会将其从集合中移除。
现在为了找到特定叶节点的答案，我需要找出 Set 中遵循 x-T <= y <= x+T 的节点数，其中 'y' 是祖先，x-T 和 x +T 是范围内的节点。
我了解 Fenwick 树的概念，但我无法设计在树中存储什么以便进行范围查询，或者具体如何进行范围查询。我了解检索总和时它是如何工作的，但是 给定一个范围 [left, right] 我如何找到存储在 tree
中的范围内的元素数我在普林斯顿算法中找到了查询芬威克树的示例。你可以在这里找到它：
http://algs4.cs.princeton.edu/99misc/FenwickTree.java.html
希望对您的上下文有所帮助。
注意标签的范围最多为10^5，所以可以将标签存储在分域树中。用1表示存在一个节点，否则为0。那么sum表示节点总数。
假设我们有 Fenwick 树 T，方法
add(pos, val), addval在位置pos, O(lgn)sum(pos)，得到位置1到pos的和，O(lgn)
while dfs，插入节点x，执行T.add(x, 1)，删除节点x，执行T.add(x, -1)，查询节点[=17] =], 即 T.sum(x+k) - T.sum(x-k-1).
有关详细信息，请参阅 code。