线段树（单点修改）

1 #include 
     
       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 
     
       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 }