• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest May 19th, 2019 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
4.
5. struct node {
6.     int left;
7.     int right;
8.     int max;
9.     node * child_left;
10.     node * child_right;
11. };
12.
13. node * build(int left, int right, std::vector<int> & a){
14.
15.     node * res = new node;
16.     res->left = left;
17.     res->right = right;
18.
19.     if (left == right){
20.         res->child_left = nullptr;
21.         res->child_right = nullptr;
22.         res->max = a[left];
23.     }   else {
24.         int mid = (left + right) / 2;
25.         res->child_left = build(left, mid, a);
26.         res->child_right = build(mid + 1, right, a);
27.         res->max = std::max(res->child_left->max, res->child_right->max);
28.     }
29.
30.     return res;
31. }
32.
33. int query(node * root, int left, int right){
34.     if (right < root->left || left > root->right){
35.         return -1;
36.     }
37.     if (left <= root->left && root->right <= right){
38.         return root->max;
39.     }
40.     int ans1 = query(root->child_left, left, right);
41.     int ans2 = query(root->child_right, left, right);
42.     return std::max(ans1, ans2);
43. }
44.
45. void update(node * root, int i, int val){
46.     if (i < root->left || i > root->right){
47.         return;
48.     }
49.     if (root->left == root->right){
50.         root->max = val;
51.         return;
52.     }
53.     update(root->child_left, i, val);
54.     update(root->child_right, i, val);
55.     root->max = std::max(root->child_right->max, root->child_left->max);
56. }
57.
58.
59. int main() {
60.     int n = 100;
61.     std::vector<int> a(n + 1);
62.     for (int i = 1; i < n + 1; ++i){
63.         a[i] = i % 10;
64.     }
65.     node * root = build(1, n, a);
66.     std::cout<<query(root, 23, 35)<<std::endl;
67.     update(root, 29, 5);
68.     std::cout<<query(root, 23, 35)<<std::endl;
69.     update(root, 31, 100);
70.     std::cout<<query(root, 23, 35)<<std::endl;
71.     return 0;
72. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top