Sort before insert — A small, yet powerful extension to Merge sort tree

Revision en4, by darkkcyan, 2020-12-12 10:34:28

Hello Codeforces!

Today I wanted to gain contributions share my small invention during my upsolving. I don't know if there existed a similar idea yet, but as far as I can tell, the editorial for the problem does not use my idea. I think it would be nice to share with you guys and have your opinions on this idea.

Idea explanation

How do we build Merge-sort tree again?

Merge sort tree is a Segment tree, each node of whose contains a sorted set/vector of every element in its range. We build it in a bottom-up manner. To build the parent nodes, we merge 2 sets/vectors of the children the same as we do in the merge-sort algorithm in $$$O(n)$$$, hence the name Merge-sort tree.

But there is another way.

Let A be the array we are building the merge-sort tree on, it[i] be the vector that contains sorted elements in the range conquer by the i-th node. Let's create another array B that stores the following pairs: B[i].first = A[i], B[i].second = i. We sort the array B in the increasing order of first. Then we iterate each pair element value, position of B in that sorted order, push the value to the back of every it[i] where i is the node of the merge-sort tree that contains position.

We can see that I sort the array before inserting, so I decided to call this trick sort before insert. Do you guys have a better name?

Some advantages of "sort before insert" over the classical way

  • We can handle the case where we have multiple element located in the same position.
  • With efficient style we can build this tree iteratively.

Here is the small snippet for building the tree.

const int N = 1e5;  // limit for array size
int n;  // array size
vector<int> it[2 * N];

void build(const vector<int>& a) {
  vector<pair<int, int>> b;
  for (int i = 0; i < (int)a.size(); ++i) {
    b.emplace_back(a[i], i);
  }
  sort(b.begin(), b.end());
  for (auto [val, p]: b) {
    for (p += (int)a.size(); p > 0; p >>= 1)
      it[p].push_back(val);
  }
}

So now we can call merge-sort tree — quick-sort tree from now :))

Can we do with ranges?

As we can see, each node in the merge-sort tree contains only elements of its range, and in the sort before insert version, we used point-update to build the tree. Can we do the same with range-like update? Yes, yes we can with sort before insert!

But what does each node contains exactly? We already know that for every interval, we can break it into $$$O(\log n)$$$ sub-intervals, each of them will correspond to a node of the segment tree. So if we have some intervals with some associated value, we can add these values to every node corresponding to the sub-interval of the considering interval, so that the vectors of the nodes will still be sorted.

Here is the implementation of the idea.

const int N = 1e5;  // limit for array size
int n;  // array size
vector<int> it[2 * N];

struct Range {
  int l, r, value;  // [l, r)
};
void build(vector<Range> a) {
  sort(a.begin(), a.end(), [](const Range& u, const Range& v) { return u.value < v.value});
  int n = (int)a.size();
  for (auto [l, r, val]: b) {
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) it[l++].push_back(val);
      if (r & 1) it[--r].push_back(val);
    }
  }
}
Tags #segment tree, #merge sort tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en25 English darkkcyan 2021-07-06 10:35:36 0 (published)
en24 English darkkcyan 2021-07-06 10:34:17 270 Add an applicable problem
en23 English darkkcyan 2021-07-06 10:29:28 454 (saved to drafts)
en22 English darkkcyan 2020-12-12 18:43:21 11 Fix typo.
en21 English darkkcyan 2020-12-12 18:40:33 12 Fix typo.
en20 English darkkcyan 2020-12-12 17:15:56 2 Fix typo.
en19 English darkkcyan 2020-12-12 17:13:46 417 Add short problem statements for the first 2 problems.
en18 English darkkcyan 2020-12-12 17:08:46 285 Add prerequisite.
en17 English darkkcyan 2020-12-12 16:58:54 2 Fix copy and paste code.
en16 English darkkcyan 2020-12-12 16:52:06 1 Fix typo.
en15 English darkkcyan 2020-12-12 16:46:04 0 (published)
en14 English darkkcyan 2020-12-12 16:45:54 64 Tiny change.
en13 English darkkcyan 2020-12-12 16:43:24 16 Tiny changes.
en12 English darkkcyan 2020-12-12 16:38:49 411 Fix typo.
en11 English darkkcyan 2020-12-12 16:18:51 672 Add summary.
en10 English darkkcyan 2020-12-12 16:10:52 1918 Add GP of NorthBeach G application.
en9 English darkkcyan 2020-12-12 15:42:19 2714 Add H 2020 HongKong regional application.
en8 English darkkcyan 2020-12-12 13:15:41 2122 Add 2D range sum application.
en7 English darkkcyan 2020-12-12 11:45:13 1027 Add MKTHNUM application.
en6 English darkkcyan 2020-12-12 11:14:41 54 Minor changes for the bulding code.
en5 English darkkcyan 2020-12-12 11:09:29 1866 Add application for KQUERY.
en4 English darkkcyan 2020-12-12 10:34:28 26 Minor changes in the building code.
en3 English darkkcyan 2020-12-12 10:29:33 1324 Add building the tree with range.
en2 English darkkcyan 2020-12-12 10:08:56 1795 Added building part for idea explaination.
en1 English darkkcyan 2020-12-12 09:45:32 423 Initial revision (saved to drafts)