线段树

亦凉 2021-12-03 07:17 388阅读 0赞

线段树（单点修改）

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 
     4 struct node {
     5     int start, end;
     6     int val;
     7     node *left, *right;
     8     node(int _start, int _end) :
     9         start(_start), end(_end), val(INT_MAX), left(NULL), right(NULL) {}
    10 };
    11 
    12 node *buildTree(int start, int end) {
    13     if (start > end) return NULL;
    14     node *root = new node(start, end);
    15     if (start == end) return root;
    16     int mid = start + ((end - start) >> 1);
    17     root->left = buildTree(start, mid);
    18     root->right = buildTree(mid + 1, end);
    19     return root;
    20 }
    21 
    22 void update(node *root, int idx, int val) {
    23     if (idx == root->start && idx == root->end) {
    24         root->val = val;
    25         return;
    26     }
    27     int mid = root->start + ((root->end - root->start) >> 1);
    28     if (idx >= root->start && idx <= mid) update(root->left, idx, val);
    29     else if (idx > mid && idx <= root->end) update(root->right, idx, val);
    30     root->val = min(root->left->val, root->right->val);
    31 }
    32 
    33 int query(node *root, int start, int end) {
    34     if (start == root->start && end == root->end) return root->val;
    35     int mid = root->start + ((root->end - root->start) >> 1);
    36     if (end <= mid) return query(root->left, start, end);
    37     if (start > mid) return query(root->right, start, end);
    38     return min(query(root->left, start, mid), query(root->right, mid + 1, end));
    39 }
    40 
    41 int N, Q;
    42 int idx, val;
    43 int op;
    44 
    45 int main() {
    46     cin >> N;
    47     node *root = buildTree(1, N);
    48     for (idx = 1; idx <= N; ++idx) {
    49         cin >> val;
    50         update(root, idx, val);
    51     }
    52     cin >> Q;
    53     for (int i = 0; i < Q; ++i) {
    54         cin >> op >> idx >> val;
    55         if (op == 0) cout << query(root, idx, val) << endl;
    56         else update(root, idx, val);
    57     }
    58     return 0;
    59 }

线段树（区间修改）

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 
     4 struct node {
     5     int start, end;
     6     int val;
     7     int tag;
     8     node *left, *right;
     9     node(int _start, int _end) :
    10         start(_start), end(_end), val(0), tag(-1),
    11         left(NULL), right(NULL) {}
    12 };
    13 
    14 node *buildTree(int start, int end) {
    15     if (start > end) return NULL;
    16     node *root = new node(start, end);
    17     if (start == end) return root;
    18     int mid = start + ((end - start) >> 1);
    19     root->left = buildTree(start, mid);
    20     root->right = buildTree(mid + 1, end);
    21     return root;
    22 }
    23 
    24 void update(node *root, int start, int end, int val) {
    25     if (start == root->start && end == root->end) {
    26         root->tag = val;
    27         root->val = val * (end - start + 1);
    28         return;
    29     }
    30     int mid = root->start + ((root->end - root->start) >> 1);
    31     if (root->tag != -1) {
    32         root->left->tag = root->tag;
    33         root->left->val = root->tag * (root->left->end - root->left->start + 1);
    34         root->right->tag = root->tag;
    35         root->right->val = root->tag * (root->right->end - root->right->start + 1);
    36         root->tag = -1;
    37     }
    38     if (end <= mid) update(root->left, start, end, val);
    39     else if (start > mid) update(root->right, start, end, val);
    40     else update(root->left, start, mid, val), update(root->right, mid + 1, end, val);
    41     root->val = root->left->val +  root->right->val;
    42 }
    43 
    44 int query(node *root, int start, int end) {
    45     if (start == root->start && end == root->end) return root->val;
    46     if (root->tag != -1) {
    47         root->left->tag = root->tag;
    48         root->left->val = root->tag * (root->left->end - root->left->start + 1);
    49         root->right->tag = root->tag;
    50         root->right->val = root->tag * (root->right->end - root->right->start + 1);
    51         root->tag = -1;
    52     }
    53     int mid = root->start + ((root->end - root->start) >> 1);
    54     if (end <= mid) return query(root->left, start, end);
    55     if (start > mid) return query(root->right, start, end);
    56     return query(root->left, start, mid) + query(root->right, mid + 1, end);
    57 }
    58 
    59 int N, Q;
    60 int idx, val, st, ed;
    61 int op;
    62 
    63 int main() {
    64     cin >> N;
    65     node *root = buildTree(1, N);
    66     for (idx = 1; idx <= N; ++idx) {
    67         cin >> val;
    68         update(root, idx, idx,  val);
    69     }
    70     cin >> Q;
    71     for (int i = 0; i < Q; ++i) {
    72         cin >> op >> st >> ed;
    73         if (op == 0) {
    74             cout << query(root, st, ed) << endl;
    75         } else {
    76             cin >> val;
    77             update(root, st, ed, val);
    78         }
    79     }
    80     return 0;
    81 }

转载于:https://www.cnblogs.com/easonliu/articles/4575506.html