thisIsMorningstar's blog

Wavelet Tree Implementation(Array Based)
By thisIsMorningstar, history, 15 months ago, In English

I recently learned wavelet trees. This data structure can handle the following types of range queries in logarithmic time:

  1. Number of elements in subarray A[L...R] that are less than or equal to y.
  2. Number of occurrences of element x in subarray A[L...R].
  3. The kth smallest element in subarray A[L...R].

But I couldn't find the array based implementation of it anywhere, and as I don't like pointers(also pointer based implementations are often slower than array based ones because of the dynamic memory allocation), I implemented it myself. Here is the implementation: https://github.com/thisIsMorningstar/Competitive_Programming/blob/main/templates/wavelet_tree.cpp

I stress tested this with a bruteforce code against a couple thousand random testcases and it passed. But if you find any bugs in it, do let me know :).

You can learn about wavelet trees from here: https://codeforces.com/blog/entry/52854

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

»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Great job man :D

→ Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Second type of query is just subset of the first type.

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't like pointers

Proceeds to use l and r array the exact same way as pointers...

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how is it exactly like pointers? ;-;

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
      ← Rev. 5   Vote: I like it +3 Vote: I do not like it

      You're using a well-known technique, which is not specific to wavelet tree. Instead of using dynamic allocation like

      struct Node {
	Node* leftPtr;
	void doSomething() {
		leftPtr = new Node(); // slow!
		leftPtr->doSomething();
	}
};

      You use indices on a big pre-allocated array (or deque) :

      struct Node {
	int leftId;
};
Node preallocated[BIG_CONSTANT]; int nxt = 0;
void doSomething(int nodeId) {
	Node& node = preallocated[nodeId];
	node.leftId = nxt++; // simulate left = new Node();
	doSomething(node.leftId);
}

      But observe that preallocated[leftId] is equivalent to *(preallocated + leftId) i.e. leftPtr = preallocated + leftId.

      You are basically using pointers but in a specific, pre-allocated memory block. It is indeed a good optimization but the idea is not really different (I would say that you "optimized" the pointers, you didn't get rid of them).

      → Reply
      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        I don't know why downvoted. Exactly what I meant.

        → Reply