I'm trying to solve this problem that involves querying a fenwick tree.
Problem statement is as follows:
This is a problem from a Hackerrank contest: link
You are given a tree where each node is labeled from 1, 2, …, n. How many similar pairs(S) are there in this tree?
A pair (A,B) is a similar pair iff
1 <= n <= 100000
0 <= T <= n
1 <= si, ei <= n.
Note the range of label is at most
10^5, so you can store the label in Fenwick tree. Using 1 to indicate the existence of a node, otherwise 0. Then sum indicates the total number of nodes.
Assume we have Fenwick tree
T, with methods
add(pos, val), add
sum(pos), get the sum of position 1 to
While dfs, when inserting a node
T.add(x, 1), when removing a node
T.add(x, -1), when do query on node
x, it is
T.sum(x+k) - T.sum(x-k-1).
See the code for more details.