Merge Sort Tree
(library/data-structure/merge-sort-tree.hpp)

• View this file on GitHub
• Last update: 2023-07-01 16:07:45+08:00
• Include: #include "library/data-structure/merge-sort-tree.hpp"

使用方法

vector<int> a = {4, 8, 7, 6, 3};

merge_sort_tree<int> tree(a);

int l, r, x;

// [l, r) 區間 < / <= / > / >= x 的元素數量
int cnt_less = tree.count_less(l, r, x);
int cnt_less_eq = tree.count_less_equal(l, r, x);
int cnt_greater = tree.count_greater(l, r, x);
int cnt_greater_eq = tree.count_greater_equal(l, r, x);

題目

SPOJ - KQUERY

References

https://hitonanode.github.io/cplib-cpp/segmenttree/merge_sort_tree.hpp

Verified with

• test/data-structure/merge-sort-tree/yosupo-Range-Kth-Smallest.test.cpp

Code

#pragma once
#include <vector>

#include <algorithm>


namespace felix {

template<class T>
struct merge_sort_tree {
public:
	merge_sort_tree() : n(0) {}
	explicit merge_sort_tree(const std::vector<T>& val) : n(val.size()), tree(val.size() * 2) {
		for(int i = 0; i < n; i++) {
			tree[n + i] = {val[i]};
		}
		for(int i = n - 1; i >= 0; i--) {
			std::merge(tree[2 * i].begin(), tree[2 * i].end(), tree[2 * i + 1].begin(), tree[2 * i + 1].end(), std::back_inserter(tree[i]));
		}
	}

	int count_less(int l, int r, T x) const {
		int ans = 0;
		for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if(l & 1) {
				ans += std::lower_bound(tree[l].begin(), tree[l].end(), x) - tree[l].begin();
				l++;
			}
			if(r & 1) {
				r--;
				ans += std::lower_bound(tree[r].begin(), tree[r].end(), x) - tree[r].begin();
			}
		}
		return ans;
	}

	int count_less_equal(int l, int r, T x) const {
		int ans = 0;
		for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if(l & 1) {
				ans += std::upper_bound(tree[l].begin(), tree[l].end(), x) - tree[l].begin();
				l++;
			}
			if(r & 1) {
				r--;
				ans += std::upper_bound(tree[r].begin(), tree[r].end(), x) - tree[r].begin();
			}
		}
		return ans;
	}

	int count_greater(int l, int r, T x) const {
		return r - l - count_less_equal(l, r, x);
	}

	int count_greater_equal(int l, int r, T x) const {
		return r - l - count_less(l, r, x);
	}

private:
	int n;
	std::vector<std::vector<T>> tree;
};

} // namespace felix

#line 2 "library/data-structure/merge-sort-tree.hpp"
#include <vector>

#include <algorithm>


namespace felix {

template<class T>
struct merge_sort_tree {
public:
	merge_sort_tree() : n(0) {}
	explicit merge_sort_tree(const std::vector<T>& val) : n(val.size()), tree(val.size() * 2) {
		for(int i = 0; i < n; i++) {
			tree[n + i] = {val[i]};
		}
		for(int i = n - 1; i >= 0; i--) {
			std::merge(tree[2 * i].begin(), tree[2 * i].end(), tree[2 * i + 1].begin(), tree[2 * i + 1].end(), std::back_inserter(tree[i]));
		}
	}

	int count_less(int l, int r, T x) const {
		int ans = 0;
		for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if(l & 1) {
				ans += std::lower_bound(tree[l].begin(), tree[l].end(), x) - tree[l].begin();
				l++;
			}
			if(r & 1) {
				r--;
				ans += std::lower_bound(tree[r].begin(), tree[r].end(), x) - tree[r].begin();
			}
		}
		return ans;
	}

	int count_less_equal(int l, int r, T x) const {
		int ans = 0;
		for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if(l & 1) {
				ans += std::upper_bound(tree[l].begin(), tree[l].end(), x) - tree[l].begin();
				l++;
			}
			if(r & 1) {
				r--;
				ans += std::upper_bound(tree[r].begin(), tree[r].end(), x) - tree[r].begin();
			}
		}
		return ans;
	}

	int count_greater(int l, int r, T x) const {
		return r - l - count_less_equal(l, r, x);
	}

	int count_greater_equal(int l, int r, T x) const {
		return r - l - count_less(l, r, x);
	}

private:
	int n;
	std::vector<std::vector<T>> tree;
};

} // namespace felix

Back to top page