class seg_tree_node {
public:
int start = 0;
int end = 0;
int val = 0;
seg_tree_node* left;
seg_tree_node* right;
seg_tree_node(int s, int e, int v, seg_tree_node* l = nullptr, seg_tree_node* r = nullptr) {
start = s;
end = e;
val = v;
left = l;
right = r;
}
};
class seg_tree {
public:
seg_tree(std::vector<int>& v) {
data.swap(v);
}
~seg_tree() {
if (root) {
clean(root);
}
}
seg_tree_node* buildTree(int start, int end) {
if (start == end)
return new seg_tree_node(start, end, data[start]);
int mid = (start + end) >> 1;
seg_tree_node* left = buildTree(start, mid);
seg_tree_node* right = buildTree(mid + 1, end);
return new seg_tree_node(start, end, left->val + right->val, left, right);
}
void updateTree(int index, int val,seg_tree_node* node) {
if (node->start == index && node->end == index) {
node->val = val;
return;
}
int mid = (node->start + node->end) >> 1;
if (index <= mid) {
updateTree(index, val, node->left);
}
else {
updateTree(index, val, node->right);
}
}
int queryTree(int s, int e, seg_tree_node* node) {
if (node->start == s && node->end == e) {
return node->val;
}
int mid = (node->start + node->end) >> 1;
if (mid < s) {
return queryTree(s, e, node->right);
}
else if (mid >= e) {
return queryTree(s, e, node->left);
}
else {
return queryTree(s, mid, node->left) + queryTree(mid + 1, e, node->right);
}
}
private:
void clean(seg_tree_node* node) {
if (!node)
return;
seg_tree_node* left = node->left;
clean(left);
seg_tree_node* right = node->right;
clean(right);
delete node;
node = nullptr;
}
private:
std::vector<int> data;
seg_tree_node* root = nullptr;
};
网友评论