### Lolcode_LL's blog

By Lolcode_LL, history, 3 weeks ago,

BIT is not a tree, but it's a forest. This way we can't find a root node, so we have to create a fake root node, to copy it and it's children. Now let's make a c++ struct, describing a BIT node.

struct node {
int id, sum;
unordered_map<int, node*> children;
};


Now, let's decide, how to do search and update queries. Let's build straight path using this build_path function

vector<int> build_path(int p, int n){
vector<int> res;
for (;p <= n; p += p & -p){
res.push_back(p);
}
return res;
}


So we have a path to go, but we haven't got a tree, lol. Let's define a build function, which works in O(N) and creates all parents for each node. It's just something like DFS, but with explicit path finding.

node *build(int n) {
bitset<int(1e5) + 5> bs;
node *root = new node();
for (int i = 1; i <= n; ++i) {
if (!bs[i]) {
vector<int> path = build_path(i, n);
int pos = int(path.size()) - 1;
node *t = root;
while (pos >= 0) {
if (!bs[path[pos]]) {
bs[path[pos]] = 1;
t->p[path[pos]] = new node();
}
t = t->p[path[pos]];
--pos;
}
}
}
return root;
}


To be continued...

P.S. Now, I understand, that copying each visited node will give us O(qlog^2(n)) memory, so I don't think, that this data structure is very useful..

• +6

 » 3 weeks ago, # |   0 There are easier implementations for Persistent BIT that can be implemented easily by sorting vector and use lower_bound() to find the answer. You said that you don't think this DS is useful. But actually the time for you to implement a persistent segment tree could be long. Why not just code a persistent BIT and save the time for thinking harder problems
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Yes, but 3 month ago, when I wrote this article, I thought, that time and memory wold be O(qlogn), not log^2