Блог пользователя thisIsMorningstar

Wavelet Tree Implementation(Array Based)
Автор thisIsMorningstar, история, 21 месяц назад, По-английски

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.net/blog/entry/52854

  • Проголосовать: нравится
  • +45
  • Проголосовать: не нравится

»
21 месяц назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Great job man :D

→ Ответить
»
21 месяц назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I don't like pointers

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

→ Ответить
  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    how is it exactly like pointers? ;-;

    → Ответить
    • »
      »
      »
      21 месяц назад, # ^ |
      ← Rev. 5   Проголосовать: нравится +3 Проголосовать: не нравится

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

      → Ответить