fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct SegmentTree {
  5.     int n;
  6.     vector<int> tree, lazy;
  7.     const int NO_UPDATE = numeric_limits<int>::max(); // Special marker
  8.  
  9.     SegmentTree(int size) {
  10.         n = size;
  11.         tree.assign(4 * n, 0);       // Default value can be changed
  12.         lazy.assign(4 * n, NO_UPDATE);
  13.     }
  14.  
  15.     void push(int node, int l, int r) {
  16.         if (lazy[node] != NO_UPDATE) {
  17.             tree[node] = lazy[node];
  18.             if (l != r) { // propagate to children
  19.                 lazy[node * 2] = lazy[node];
  20.                 lazy[node * 2 + 1] = lazy[node];
  21.             }
  22.             lazy[node] = NO_UPDATE;
  23.         }
  24.     }
  25.  
  26.     void rangeSet(int node, int l, int r, int ql, int qr, int val) {
  27.         push(node, l, r);
  28.         if (qr < l || r < ql) return;
  29.         if (ql <= l && r <= qr) {
  30.             lazy[node] = val;
  31.             push(node, l, r);
  32.             return;
  33.         }
  34.         int mid = (l + r) / 2;
  35.         rangeSet(node * 2, l, mid, ql, qr, val);
  36.         rangeSet(node * 2 + 1, mid + 1, r, ql, qr, val);
  37.     }
  38.  
  39.     int pointQuery(int node, int l, int r, int idx) {
  40.         push(node, l, r);
  41.         if (l == r) return tree[node];
  42.         int mid = (l + r) / 2;
  43.         if (idx <= mid)
  44.             return pointQuery(node * 2, l, mid, idx);
  45.         else
  46.             return pointQuery(node * 2 + 1, mid + 1, r, idx);
  47.     }
  48.  
  49.     // Public interfaces
  50.     void rangeSet(int l, int r, int val) {
  51.         rangeSet(1, 0, n - 1, l, r, val);
  52.     }
  53.  
  54.     int pointQuery(int idx) {
  55.         return pointQuery(1, 0, n - 1, idx);
  56.     }
  57. };
  58.  
  59.  
  60. int main() {
  61.     SegmentTree st(10);
  62.  
  63.     st.rangeSet(2, 5, 7);     // set elements in range [2, 5] to 7
  64.     st.rangeSet(4, 9, 3);     // set elements in range [4, 9] to 3
  65.  
  66.     for (int i = 0; i < 10; ++i) {
  67.         printf("Index %d: %d\n", i, st.pointQuery(i));
  68.     }
  69.  
  70.     return 0;
  71. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Index 0: 0
Index 1: 0
Index 2: 7
Index 3: 7
Index 4: 3
Index 5: 3
Index 6: 3
Index 7: 3
Index 8: 3
Index 9: 3
https://ideone.com/sPhkQW
language:
C++14 (gcc 8.3)
created:
19 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!