Created
October 13, 2014 08:32
-
-
Save sparfenyuk/39e7bc40f415f588116b to your computer and use it in GitHub Desktop.
Find min in segment tree
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <iterator> | |
| #include <deque> | |
| #include <vector> | |
| #include <algorithm> | |
| #include <cassert> | |
| #include <cmath> | |
| using namespace std; | |
| typedef unsigned long long input_type; | |
| typedef vector<input_type> InputContainer; | |
| #define MAX_VALUE -1ull | |
| struct Data | |
| { | |
| input_type start_index; | |
| input_type power; | |
| input_type size; | |
| InputContainer segment_tree; | |
| }; | |
| input_type get_left_child_index(input_type index) | |
| { | |
| return index * 2 + 1; | |
| } | |
| input_type get_parent_index(input_type i) | |
| { | |
| if (i % 2 == 0) { | |
| return (i - 1) / 2; | |
| } | |
| return i / 2; | |
| } | |
| bool update_min_value(Data& tree, input_type parent_index) | |
| { | |
| InputContainer& p = tree.segment_tree; | |
| input_type left_index = get_left_child_index(parent_index); | |
| input_type new_value = std::min(p[left_index], p[left_index+1]); | |
| bool is_same_value = p[parent_index] == new_value; | |
| p[parent_index] = new_value; | |
| return !is_same_value; | |
| } | |
| void set_value(Data& tree, input_type index, input_type value) | |
| { | |
| index -= 1; | |
| input_type i = tree.start_index + index; | |
| tree.segment_tree[i] = value; | |
| while (i != 0) { | |
| input_type parent_index = get_parent_index(i); | |
| if (!update_min_value(tree, parent_index)) | |
| break; | |
| i = parent_index; | |
| }; | |
| } | |
| input_type get_min(Data& tree, input_type left_b, input_type right_b, input_type current_deep, input_type current_node, input_type begin_index, input_type segment); | |
| input_type get_min(Data& tree, input_type left_b, input_type right_b) | |
| { | |
| assert(left_b > 0 && right_b > 0); | |
| --left_b; --right_b; | |
| // cout << "Start find for tree " << tree.size << endl; | |
| // cout << " in range (" << left_b << ", " << right_b << ")" << endl; | |
| input_type v = get_min(tree, left_b, right_b, 0, 0, 0, tree.size); | |
| // cout << "Result: " << v <<endl<< endl; | |
| return v; | |
| } | |
| input_type get_min(Data& tree, input_type left_b, input_type right_b, input_type current_deep, input_type current_node, input_type begin_index, input_type segment) | |
| { | |
| assert(left_b <= right_b); | |
| if (left_b == right_b) { | |
| assert(tree.start_index + left_b < tree.segment_tree.size()); | |
| // cout << "Got value for (" << left_b << ", " << right_b << "), in node=" << current_node << ": " << tree.segment_tree[tree.start_index + left_b] << endl; | |
| return tree.segment_tree[tree.start_index + left_b]; | |
| } | |
| assert(segment != 0); | |
| input_type dist = right_b - left_b; | |
| input_type half = segment / 2; | |
| if (dist + 1 == segment) { | |
| // cout << "Got value for (" << left_b << ", " << right_b << "), in node=" << current_node << ": " << tree.segment_tree[tree.start_index + left_b] << endl; | |
| assert(current_node < tree.segment_tree.size()); | |
| return tree.segment_tree[current_node]; | |
| } | |
| // cout << "Enter in range (" << begin_index << ", " << begin_index + half << ")" << endl; | |
| input_type left_child = get_left_child_index(current_node); | |
| if (left_b < half + begin_index && right_b >= half + begin_index) { | |
| input_type left = get_min(tree, left_b, begin_index + half - 1, current_deep + 1, left_child, begin_index, half); | |
| input_type right = get_min(tree, begin_index + half, right_b, current_deep + 1, left_child + 1, begin_index + half, half); | |
| // cout << "Got value for (" << left_b << ", " << right_b << "), in node=" << current_node << ": " << std::min(left, right) << endl; | |
| return std::min(left, right); | |
| } | |
| else { | |
| if (left_b < begin_index + half) { | |
| return get_min(tree, left_b, right_b, current_deep + 1, left_child, begin_index, half); | |
| } | |
| else { | |
| return get_min(tree, left_b, right_b, current_deep + 1, left_child + 1, begin_index + half, half); | |
| } | |
| } | |
| } | |
| void prepare_tree(Data& tree, input_type num) | |
| { | |
| input_type size = 1, start_index = 0, power = 0; | |
| while (size - start_index < num) { | |
| start_index = size; | |
| size = 2 * size + 1; | |
| ++power; | |
| } | |
| tree.start_index = start_index; | |
| tree.power = power; | |
| tree.size = size - start_index; | |
| tree.segment_tree.resize(size, MAX_VALUE); | |
| } | |
| int main() | |
| { | |
| // { | |
| // Data tree; | |
| // input_type i = 1; | |
| // prepare_tree(tree, 1); | |
| // set_value(tree, i++, 1); | |
| // assert(get_min(tree, 1, 1) == 1); | |
| // } | |
| // { | |
| // Data tree; | |
| // input_type i = 1; | |
| // prepare_tree(tree, 2); | |
| // set_value(tree, i++, 1); | |
| // set_value(tree, i++, 2); | |
| // assert(get_min(tree, 1, 1) == 1); | |
| // assert(get_min(tree, 2, 2) == 2); | |
| // assert(get_min(tree, 1, 2) == 1); | |
| // } | |
| // { | |
| // Data tree; | |
| // input_type i = 1, j = 10001; | |
| // prepare_tree(tree, j); | |
| // for (input_type k = 0; k < j; ++k) { | |
| // set_value(tree, k+1, j); | |
| // } | |
| // assert(get_min(tree, 1, 1) == j); | |
| // assert(get_min(tree, 1, j) == j); | |
| // assert(get_min(tree, j/3, j/2) == j); | |
| // assert(get_min(tree, j/3*2, j) == j); | |
| // assert(get_min(tree, j-2, j) == j); | |
| // assert(get_min(tree, j-3, j) == j); | |
| // assert(get_min(tree, j-j/10, j-j/20) == j); | |
| // assert(get_min(tree, j-j/25, j-j/30) == j); | |
| // assert(get_min(tree, j/2-0, j-j/30) == j); | |
| // | |
| // } | |
| // { | |
| // Data tree; | |
| // input_type i = 1; | |
| // prepare_tree(tree, 5); | |
| // set_value(tree, i++, 1); | |
| // set_value(tree, i++, 2); | |
| // set_value(tree, i++, 3); | |
| // set_value(tree, i++, 4); | |
| // set_value(tree, i++, 5); | |
| // assert(get_min(tree, 1, 5) == 1); | |
| // set_value(tree, 1, 8); | |
| // assert(get_min(tree, 1, 5) == 2); | |
| // assert(get_min(tree, 1, 1) == 8); | |
| // assert(get_min(tree, 1, 3) == 2); | |
| // set_value(tree, 3, 1); | |
| // assert(get_min(tree, 2, 4) == 1); | |
| // } | |
| // return 0; | |
| input_type n = 0, m = 0; | |
| cin >> n >> m; | |
| Data input; | |
| prepare_tree(input, n); | |
| vector<input_type> output; | |
| for (input_type i = 0; i < n; ++i) { | |
| input_type value = 0; | |
| if (cin >> value) { | |
| set_value(input, i + 1, value); | |
| } | |
| else { | |
| return 1; | |
| } | |
| } | |
| for (input_type i = 0; i < m; ++i) { | |
| string cmd; | |
| input_type first, second; | |
| cin >> cmd >> first >> second; | |
| if (cmd[0] == 'M') { | |
| input_type value = get_min(input, first, second); | |
| output.push_back(value); | |
| } | |
| else if (cmd[0] == 'S') { | |
| set_value(input, first, second); | |
| } | |
| } | |
| for (input_type i = 0, size = output.size(); i < size; ++i) { | |
| if (output[0] == 0) { | |
| continue; | |
| } | |
| cout << output[i] << endl; | |
| } | |
| return 0; | |
| } | |
| /* | |
| Sample Input: | |
| 5 7 | |
| 1 2 3 4 5 | |
| Min 1 5 | |
| Set 1 8 | |
| Min 1 5 | |
| Min 1 1 | |
| Min 1 3 | |
| Set 3 1 | |
| Min 2 4 | |
| Sample Output: | |
| 1 | |
| 2 | |
| 8 | |
| 2 | |
| 1 | |
| */ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment