Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
template<typename T, const T& Combine(const T&, const T&)>
class segment_tree {
darray<T> v;
T default_value;
T combine_considering_default(const T& left_value, const T& right_value) const {
if (left_value == default_value) {
return right_value;
} else if (right_value == default_value) {
return left_value;
} else {
return Combine(left_value, right_value);
}
}
public:
explicit segment_tree(usize size) : default_value(T()) {
v.reserve(size << 1u);
for (usize i = 0u; i < size; i++) v.push_back(default_value);
for (usize i = 0u; i < size; i++) v.push_back(default_value);
}
segment_tree(usize size, T default_value) : default_value(default_value) {
v.reserve(size << 1u);
for (usize i = 0u; i < size; i++) v.push_back(default_value);
for (usize i = 0u; i < size; i++) v.push_back(default_value);
}
explicit segment_tree(const darray<T>& values_src) : default_value(T()) {
v.reserve(values_src.size() << 1u);
for (usize i = 0u; i < values_src.size(); i++) v.push_back(default_value);
for (usize i = 0u; i < values_src.size(); i++) v.push_back(values_src[i]);
update_all();
}
segment_tree(const darray<T>& values_src, T default_value) : default_value(default_value) {
v.reserve(values_src.size() << 1u);
for (usize i = 0u; i < values_src.size(); i++) v.push_back(default_value);
for (usize i = 0u; i < values_src.size(); i++) v.push_back(values_src[i]);
update_all();
}
segment_tree(const segment_tree& src) : v(src.v), default_value(src.default_value) {}
segment_tree(segment_tree&& src) noexcept : v(move(src.v)), default_value(move(src.default_value)) {}
segment_tree& operator=(const segment_tree& src) { self = segment_tree(src); return self; }
segment_tree& operator=(segment_tree&& src) noexcept { v = move(src.v); default_value = move(src.default_value); return self; }
void modify_without_update(usize i, const T& value) {
v[(v.size() >> 1u) + i] = value;
}
void modify(usize i, const T& value) {
modify_without_update(i, move(value));
for (usize v_index = ((v.size() >> 1u) + i >> 1u); v_index > 0u; v_index >>= 1u) {
update(v_index);
}
}
void update(usize v_index) {
if (v_index == 0u || v_index >= (v.size() >> 1u)) return;
v[v_index] = combine_considering_default(v[(v_index << 1u)], v[(v_index << 1u) | 1u]);
}
void update_all() {
for (usize v_index = (v.size() >> 1u) - 1u; v_index > 0u; v_index--) update(v_index);
}
T query(usize begin, usize end) const {
T result_left = default_value;
T result_right = default_value;
for (usize left = begin + (v.size() >> 1u), right = end + (v.size() >> 1u); left < right; left >>= 1u, right >>= 1u) {
if (left & 1u) {
result_left = combine_considering_default(result_left, v[left]);
left++;
}
if (right & 1u) {
result_right = combine_considering_default(v[right - 1u], result_right);
right--;
}
}
return combine_considering_default(result_left, result_right);
}
};
@kyaryunha

This comment has been minimized.

Copy link

commented Jun 21, 2019

파차귀여워~~

@souldomination

This comment has been minimized.

Copy link

commented Jun 21, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.