Lolcode_LL's blog

By Lolcode_LL, history, 3 weeks ago, In English

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..

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    Yes, but 3 month ago, when I wrote this article, I thought, that time and memory wold be O(qlogn), not log^2