fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. // =====================================================================
  7. // This file provides a collection of ready‑to‑use segment tree
  8. // implementations.  Each class is a "black box" – you only need to
  9. // know what it does, how to call its methods, and what to expect.
  10. // All comments above each class/method explain exactly that.
  11. // =====================================================================
  12.  
  13. // ---------------------------------------------------------------------
  14. // 1) Basic Iterative Segment Tree – Range Sum with Point Updates
  15. //    Use when you need to:
  16. //      - change one element in the array (point update)
  17. //      - ask for the sum of any interval [l, r]
  18. //    Very fast and simple.
  19. // ---------------------------------------------------------------------
  20.  
  21. struct SegTreeSum {
  22.     // -----------------------------------------------------------------
  23.     // Purpose:
  24.     //   Maintains an array of numbers.  Supports:
  25.     //     - point update: set arr[pos] = new_value
  26.     //     - range sum  : sum of arr[l] + ... + arr[r]
  27.     // -----------------------------------------------------------------
  28.     // How to use:
  29.     //   1) Create object: SegTreeSum st(my_vector);
  30.     //   2) st.update(pos, value)  – pos is 0‑indexed
  31.     //   3) st.query(l, r)         – inclusive, 0‑indexed; returns sum
  32.     // -----------------------------------------------------------------
  33.     // Time Complexity:
  34.     //   Both update and query run in O(log n), where n is array size.
  35.     // -----------------------------------------------------------------
  36.     // Constraints:
  37.     //   - array size is fixed after construction.
  38.     //   - values fit in long long (64‑bit).
  39.     // -----------------------------------------------------------------
  40.     int n;
  41.     vector<ll> tree;
  42.     SegTreeSum() {}
  43.     SegTreeSum(const vector<ll>& a) { build(a); }
  44.     void build(const vector<ll>& a) {
  45.         n = 1;
  46.         while (n < (int)a.size()) n <<= 1;
  47.         tree.assign(2*n, 0);
  48.         for (int i = 0; i < (int)a.size(); i++) tree[n+i] = a[i];
  49.         for (int i = n-1; i > 0; i--) tree[i] = tree[i<<1] + tree[i<<1|1];
  50.     }
  51.     void update(int pos, ll val) {
  52.         pos += n;
  53.         tree[pos] = val;
  54.         for (pos >>= 1; pos; pos >>= 1) tree[pos] = tree[pos<<1] + tree[pos<<1|1];
  55.     }
  56.     ll query(int l, int r) { // inclusive
  57.         l += n; r += n;
  58.         ll res = 0;
  59.         while (l <= r) {
  60.             if (l & 1) res += tree[l++];
  61.             if (!(r & 1)) res += tree[r--];
  62.             l >>= 1; r >>= 1;
  63.         }
  64.         return res;
  65.     }
  66. };
  67.  
  68. // ---------------------------------------------------------------------
  69. // 2) Basic Iterative Segment Tree – Range Minimum with Point Updates
  70. //    Same as above but query returns the minimum value on the interval.
  71. // ---------------------------------------------------------------------
  72.  
  73. struct SegTreeMin {
  74.     // -----------------------------------------------------------------
  75.     // Purpose:
  76.     //   Maintains an array of numbers.  Supports:
  77.     //     - point update: set arr[pos] = new_value
  78.     //     - range minimum: min(arr[l..r])
  79.     // -----------------------------------------------------------------
  80.     // How to use:
  81.     //   1) Create object: SegTreeMin st(my_vector);
  82.     //   2) st.update(pos, value)  – pos is 0‑indexed
  83.     //   3) st.query(l, r)         – inclusive, 0‑indexed; returns minimum
  84.     // -----------------------------------------------------------------
  85.     // Time Complexity: O(log n) per operation.
  86.     // Constraints: values fit in long long.
  87.     // -----------------------------------------------------------------
  88.     int n;
  89.     vector<ll> tree;
  90.     SegTreeMin() {}
  91.     SegTreeMin(const vector<ll>& a) { build(a); }
  92.     void build(const vector<ll>& a) {
  93.         n = 1;
  94.         while (n < (int)a.size()) n <<= 1;
  95.         tree.assign(2*n, LLONG_MAX);
  96.         for (int i = 0; i < (int)a.size(); i++) tree[n+i] = a[i];
  97.         for (int i = n-1; i > 0; i--) tree[i] = min(tree[i<<1], tree[i<<1|1]);
  98.     }
  99.     void update(int pos, ll val) {
  100.         pos += n;
  101.         tree[pos] = val;
  102.         for (pos >>= 1; pos; pos >>= 1) tree[pos] = min(tree[pos<<1], tree[pos<<1|1]);
  103.     }
  104.     ll query(int l, int r) {
  105.         l += n; r += n;
  106.         ll res = LLONG_MAX;
  107.         while (l <= r) {
  108.             if (l & 1) res = min(res, tree[l++]);
  109.             if (!(r & 1)) res = min(res, tree[r--]);
  110.             l >>= 1; r >>= 1;
  111.         }
  112.         return res;
  113.     }
  114. };
  115.  
  116. // (Range Maximum is analogous – you can copy and change min to max.)
  117.  
  118. // ---------------------------------------------------------------------
  119. // 3) Lazy Segment Tree – Range Add & Range Sum (recursive)
  120. //    Use when you need to add a value to all elements in an interval
  121. //    and also query the sum of any interval.
  122. // ---------------------------------------------------------------------
  123.  
  124. struct LazySegTreeSum {
  125.     // -----------------------------------------------------------------
  126.     // Purpose:
  127.     //   Maintains an array.  Supports two operations on a range:
  128.     //     - range add: increase every element in [l, r] by a given value
  129.     //     - range sum: compute sum of elements in [l, r]
  130.     //   Both are O(log n).
  131.     // -----------------------------------------------------------------
  132.     // How to use:
  133.     //   1) Create: LazySegTreeSum st(my_vector);
  134.     //   2) st.range_add(l, r, delta)   – add delta to indices [l, r]
  135.     //   3) st.range_sum(l, r)          – return sum on [l, r]
  136.     //   All indices are 0‑based and inclusive.
  137.     // -----------------------------------------------------------------
  138.     // Time Complexity: O(log n) per range_add and range_sum.
  139.     // Constraints: n >= 1; values fit in long long.
  140.     // Note: This is a recursive implementation, recursion depth is O(log n).
  141.     // -----------------------------------------------------------------
  142.     int n;
  143.     vector<ll> tree, lazy;
  144.     LazySegTreeSum(const vector<ll>& a) {
  145.         n = a.size();
  146.         tree.assign(4*n, 0);
  147.         lazy.assign(4*n, 0);
  148.         build(1, 0, n-1, a);
  149.     }
  150.     void build(int node, int l, int r, const vector<ll>& a) {
  151.         if (l == r) {
  152.             tree[node] = a[l];
  153.             return;
  154.         }
  155.         int mid = (l+r)/2;
  156.         build(node*2, l, mid, a);
  157.         build(node*2+1, mid+1, r, a);
  158.         tree[node] = tree[node*2] + tree[node*2+1];
  159.     }
  160.     void apply(int node, int l, int r, ll val) {
  161.         tree[node] += val * (r - l + 1);
  162.         lazy[node] += val;
  163.     }
  164.     void push(int node, int l, int r) {
  165.         if (lazy[node] != 0 && l != r) {
  166.             int mid = (l+r)/2;
  167.             apply(node*2, l, mid, lazy[node]);
  168.             apply(node*2+1, mid+1, r, lazy[node]);
  169.             lazy[node] = 0;
  170.         }
  171.     }
  172.     void range_add(int L, int R, ll val) { range_add(1, 0, n-1, L, R, val); }
  173.     void range_add(int node, int l, int r, int L, int R, ll val) {
  174.         if (L > r || R < l) return;
  175.         if (L <= l && r <= R) {
  176.             apply(node, l, r, val);
  177.             return;
  178.         }
  179.         push(node, l, r);
  180.         int mid = (l+r)/2;
  181.         range_add(node*2, l, mid, L, R, val);
  182.         range_add(node*2+1, mid+1, r, L, R, val);
  183.         tree[node] = tree[node*2] + tree[node*2+1];
  184.     }
  185.     ll range_sum(int L, int R) { return range_sum(1, 0, n-1, L, R); }
  186.     ll range_sum(int node, int l, int r, int L, int R) {
  187.         if (L > r || R < l) return 0;
  188.         if (L <= l && r <= R) return tree[node];
  189.         push(node, l, r);
  190.         int mid = (l+r)/2;
  191.         return range_sum(node*2, l, mid, L, R) +
  192.                range_sum(node*2+1, mid+1, r, L, R);
  193.     }
  194. };
  195.  
  196. // ---------------------------------------------------------------------
  197. // 4) Lazy Segment Tree – Range Assignment & Range Sum
  198. //    Similar to above but the operation is "set all elements in [l, r]
  199. //    to a given value" (not add).
  200. // ---------------------------------------------------------------------
  201.  
  202. struct LazySegTreeAssign {
  203.     // -----------------------------------------------------------------
  204.     // Purpose:
  205.     //   Maintains an array.  Supports:
  206.     //     - range assign: set all elements in [l, r] to a given value
  207.     //     - range sum   : sum of elements in [l, r]
  208.     //   Both O(log n).
  209.     // -----------------------------------------------------------------
  210.     // How to use:
  211.     //   1) Create: LazySegTreeAssign st(my_vector);
  212.     //   2) st.range_set(l, r, value)   – assigns [l, r] to 'value'
  213.     //   3) st.range_sum(l, r)          – returns sum on [l, r]
  214.     //   Indices are 0‑based and inclusive.
  215.     // -----------------------------------------------------------------
  216.     // Time Complexity: O(log n) per operation.
  217.     // Constraints: n >= 1; values fit in long long.
  218.     // Note: The lazy tag indicates an assignment; it overrides any previous
  219.     //       additions (but this implementation only does assignment).
  220.     // -----------------------------------------------------------------
  221.     int n;
  222.     vector<ll> tree, lazy;
  223.     vector<bool> hasLazy; // true if lazy holds a pending assignment
  224.     LazySegTreeAssign(const vector<ll>& a) {
  225.         n = a.size();
  226.         tree.assign(4*n, 0);
  227.         lazy.assign(4*n, 0);
  228.         hasLazy.assign(4*n, false);
  229.         build(1, 0, n-1, a);
  230.     }
  231.     void build(int node, int l, int r, const vector<ll>& a) {
  232.         if (l == r) {
  233.             tree[node] = a[l];
  234.             return;
  235.         }
  236.         int mid = (l+r)/2;
  237.         build(node*2, l, mid, a);
  238.         build(node*2+1, mid+1, r, a);
  239.         tree[node] = tree[node*2] + tree[node*2+1];
  240.     }
  241.     void apply(int node, int l, int r, ll val) {
  242.         tree[node] = val * (r - l + 1);
  243.         lazy[node] = val;
  244.         hasLazy[node] = true;
  245.     }
  246.     void push(int node, int l, int r) {
  247.         if (hasLazy[node] && l != r) {
  248.             int mid = (l+r)/2;
  249.             apply(node*2, l, mid, lazy[node]);
  250.             apply(node*2+1, mid+1, r, lazy[node]);
  251.             hasLazy[node] = false;
  252.         }
  253.     }
  254.     void range_set(int L, int R, ll val) { range_set(1, 0, n-1, L, R, val); }
  255.     void range_set(int node, int l, int r, int L, int R, ll val) {
  256.         if (L > r || R < l) return;
  257.         if (L <= l && r <= R) {
  258.             apply(node, l, r, val);
  259.             return;
  260.         }
  261.         push(node, l, r);
  262.         int mid = (l+r)/2;
  263.         range_set(node*2, l, mid, L, R, val);
  264.         range_set(node*2+1, mid+1, r, L, R, val);
  265.         tree[node] = tree[node*2] + tree[node*2+1];
  266.     }
  267.     ll range_sum(int L, int R) { return range_sum(1, 0, n-1, L, R); }
  268.     ll range_sum(int node, int l, int r, int L, int R) {
  269.         if (L > r || R < l) return 0;
  270.         if (L <= l && r <= R) return tree[node];
  271.         push(node, l, r);
  272.         int mid = (l+r)/2;
  273.         return range_sum(node*2, l, mid, L, R) +
  274.                range_sum(node*2+1, mid+1, r, L, R);
  275.     }
  276. };
  277.  
  278. // ---------------------------------------------------------------------
  279. // 5) Segment Tree with Custom Monoid (template)
  280. //    This is a generic iterative segment tree that works for any
  281. //    associative operation (like sum, min, max, gcd, xor, etc.).
  282. // ---------------------------------------------------------------------
  283.  
  284. template<typename T, T (*combine)(T, T), T (*identity)()>
  285. struct SegTreeMonoid {
  286.     // -----------------------------------------------------------------
  287.     // Purpose:
  288.     //   A generic segment tree that can answer range queries for any
  289.     //   associative binary operation (e.g., sum, max, gcd).
  290.     //   The operation must be associative and have an identity element.
  291.     //   Supports point updates and range queries.
  292.     // -----------------------------------------------------------------
  293.     // How to use:
  294.     //   1) Define a combine function: T my_combine(T a, T b) { ... }
  295.     //   2) Define an identity function: T my_identity() { return ...; }
  296.     //   3) Create: SegTreeMonoid<T, my_combine, my_identity> st(vec);
  297.     //   4) st.update(pos, new_value)
  298.     //   5) st.query(l, r) returns combine over [l, r] (inclusive).
  299.     //   Indices are 0‑based.
  300.     // -----------------------------------------------------------------
  301.     // Time Complexity: O(log n) per update and query.
  302.     // Constraints:
  303.     //   - The operation must be associative.
  304.     //   - The identity must be a true identity: combine(x, identity) = x.
  305.     //   - The tree stores values of type T.
  306.     // -----------------------------------------------------------------
  307.     // Note: For non‑commutative operations (e.g., matrix multiplication),
  308.     //       the order of combination is preserved correctly.
  309.     // -----------------------------------------------------------------
  310.     int n;
  311.     vector<T> tree;
  312.     SegTreeMonoid(const vector<T>& a) { build(a); }
  313.     void build(const vector<T>& a) {
  314.         n = 1;
  315.         while (n < (int)a.size()) n <<= 1;
  316.         tree.assign(2*n, identity());
  317.         for (int i = 0; i < (int)a.size(); i++) tree[n+i] = a[i];
  318.         for (int i = n-1; i > 0; i--) tree[i] = combine(tree[i<<1], tree[i<<1|1]);
  319.     }
  320.     void update(int pos, T val) {
  321.         pos += n;
  322.         tree[pos] = val;
  323.         for (pos >>= 1; pos; pos >>= 1) tree[pos] = combine(tree[pos<<1], tree[pos<<1|1]);
  324.     }
  325.     T query(int l, int r) {
  326.         l += n; r += n;
  327.         T resL = identity(), resR = identity();
  328.         while (l <= r) {
  329.             if (l & 1) resL = combine(resL, tree[l++]);
  330.             if (!(r & 1)) resR = combine(tree[r--], resR);
  331.             l >>= 1; r >>= 1;
  332.         }
  333.         return combine(resL, resR);
  334.     }
  335. };
  336.  
  337. // Example: sum monoid
  338. ll sum_ll(ll a, ll b) { return a + b; }
  339. ll zero_ll() { return 0; }
  340. using SegTreeSumMonoid = SegTreeMonoid<ll, sum_ll, zero_ll>;
  341.  
  342. // Example: max monoid
  343. ll max_ll(ll a, ll b) { return max(a, b); }
  344. ll neg_inf() { return LLONG_MIN; }
  345. using SegTreeMax = SegTreeMonoid<ll, max_ll, neg_inf>;
  346.  
  347. // ---------------------------------------------------------------------
  348. // 6) Merge Sort Tree
  349. //    Each node stores a sorted vector of its segment.  Allows counting
  350. //    how many numbers in a range are ≤ a given value, and finding the
  351. //    k‑th smallest in a range (with binary search).
  352. // ---------------------------------------------------------------------
  353.  
  354. struct MergeSortTree {
  355.     // -----------------------------------------------------------------
  356.     // Purpose:
  357.     //   Builds a segment tree where every node contains a sorted list
  358.     //   of the elements in its segment.  Enables:
  359.     //     - count of elements ≤ x in [l, r]
  360.     //     - k‑th smallest element in [l, r] (via binary search)
  361.     //   All operations are O(log² n) (the count query) or O(log n * log V)
  362.     //   for k‑th (where V is value range).
  363.     // -----------------------------------------------------------------
  364.     // How to use:
  365.     //   1) Create: MergeSortTree mst(my_int_vector);
  366.     //   2) mst.query_le(l, r, x)   – returns count of values ≤ x in [l, r]
  367.     //   3) mst.query_kth(l, r, k)  – returns the k‑th smallest (1‑indexed)
  368.     //   Indices are 0‑based, inclusive.
  369.     // -----------------------------------------------------------------
  370.     // Time Complexity:
  371.     //   - query_le: O(log² n) (each level does a binary search)
  372.     //   - query_kth: O(log n * log V) where V is the value range (1e9)
  373.     //     because it binary searches the answer and calls query_le each time.
  374.     // -----------------------------------------------------------------
  375.     // Constraints:
  376.     //   - Values must be in the range [-1e9, 1e9] (adjustable in query_kth).
  377.     //   - n up to ~1e5 (memory ~ n log n).
  378.     // -----------------------------------------------------------------
  379.     // Note: The tree stores ints; for long long adapt accordingly.
  380.     // -----------------------------------------------------------------
  381.     int n;
  382.     vector<vector<int>> tree;
  383.     MergeSortTree(const vector<int>& a) {
  384.         n = 1;
  385.         while (n < (int)a.size()) n <<= 1;
  386.         tree.resize(2*n);
  387.         for (int i = 0; i < (int)a.size(); i++) tree[n+i] = {a[i]};
  388.         for (int i = n-1; i > 0; i--) {
  389.             tree[i].resize(tree[i<<1].size() + tree[i<<1|1].size());
  390.             merge(tree[i<<1].begin(), tree[i<<1].end(),
  391.                   tree[i<<1|1].begin(), tree[i<<1|1].end(),
  392.                   tree[i].begin());
  393.         }
  394.     }
  395.     int query_le(int l, int r, int x) {
  396.         l += n; r += n;
  397.         int res = 0;
  398.         while (l <= r) {
  399.             if (l & 1) {
  400.                 res += upper_bound(tree[l].begin(), tree[l].end(), x) - tree[l].begin();
  401.                 l++;
  402.             }
  403.             if (!(r & 1)) {
  404.                 res += upper_bound(tree[r].begin(), tree[r].end(), x) - tree[r].begin();
  405.                 r--;
  406.             }
  407.             l >>= 1; r >>= 1;
  408.         }
  409.         return res;
  410.     }
  411.     int query_kth(int l, int r, int k) {
  412.         int low = -1e9, high = 1e9;
  413.         while (low < high) {
  414.             int mid = low + (high - low) / 2;
  415.             if (query_le(l, r, mid) >= k) high = mid;
  416.             else low = mid + 1;
  417.         }
  418.         return low;
  419.     }
  420. };
  421.  
  422. // ---------------------------------------------------------------------
  423. // 7) Fenwick Tree (Binary Indexed Tree)
  424. //    Often used for frequency counting after coordinate compression.
  425. //    Supports point updates and prefix sums, plus finding k‑th element.
  426. // ---------------------------------------------------------------------
  427.  
  428. struct Fenwick {
  429.     // -----------------------------------------------------------------
  430.     // Purpose:
  431.     //   A Fenwick tree (BIT) for 1‑indexed arrays.  Supports:
  432.     //     - add value delta at position idx
  433.     //     - prefix sum up to idx
  434.     //     - range sum [l, r]
  435.     //     - find smallest idx with prefix sum >= k (k‑th order statistic)
  436.     //   Very efficient and simple.
  437.     // -----------------------------------------------------------------
  438.     // How to use:
  439.     //   1) Create: Fenwick fw(n)  – where n is the maximum index (1‑based)
  440.     //   2) fw.add(idx, delta)     – idx is 1‑based
  441.     //   3) fw.sum(idx)            – returns sum of positions 1..idx
  442.     //   4) fw.range_sum(l, r)     – sum on [l, r] (1‑based, inclusive)
  443.     //   5) fw.kth(k)              – returns smallest idx with prefix sum ≥ k
  444.     // -----------------------------------------------------------------
  445.     // Time Complexity: O(log n) per operation.
  446.     // Constraints: n >= 1; all internal values fit in int (or long long).
  447.     // Note: The kth method uses binary lifting and requires that all
  448.     //       values are non‑negative and the total sum >= k.
  449.     // -----------------------------------------------------------------
  450.     int n;
  451.     vector<int> bit;
  452.     Fenwick(int n) : n(n), bit(n+1, 0) {}
  453.     void add(int idx, int delta) {
  454.         for (; idx <= n; idx += idx & -idx) bit[idx] += delta;
  455.     }
  456.     int sum(int idx) {
  457.         int res = 0;
  458.         for (; idx > 0; idx -= idx & -idx) res += bit[idx];
  459.         return res;
  460.     }
  461.     int range_sum(int l, int r) {
  462.         if (l > r) return 0;
  463.         return sum(r) - sum(l-1);
  464.     }
  465.     int kth(int k) {
  466.         int idx = 0;
  467.         int mask = 1 << (31 - __builtin_clz(n));
  468.         while (mask) {
  469.             int nxt = idx + mask;
  470.             if (nxt <= n && bit[nxt] < k) {
  471.                 idx = nxt;
  472.                 k -= bit[nxt];
  473.             }
  474.             mask >>= 1;
  475.         }
  476.         return idx + 1;
  477.     }
  478. };
  479.  
  480. // ---------------------------------------------------------------------
  481. // 8) Dynamic Segment Tree (point update, range sum over large coordinates)
  482. //    Creates nodes only when needed, so you can use it even if the
  483. //    coordinate range is huge (e.g., up to 1e9).
  484. // ---------------------------------------------------------------------
  485.  
  486. struct DynamicSegTree {
  487.     // -----------------------------------------------------------------
  488.     // Purpose:
  489.     //   A segment tree that does not pre‑allocate a full array.
  490.     //   It builds nodes on demand, so it can work with very large
  491.     //   index ranges (e.g., n up to 1e9) while using memory proportional
  492.     //   to the number of updates.
  493.     //   Supports point updates (set value) and range sum queries.
  494.     // -----------------------------------------------------------------
  495.     // How to use:
  496.     //   1) Create: DynamicSegTree dseg(n)  – where n is the size (0..n-1)
  497.     //   2) dseg.update(pos, value)         – pos is 0‑based
  498.     //   3) dseg.query(L, R)                – returns sum on [L, R]
  499.     // -----------------------------------------------------------------
  500.     // Time Complexity: O(log n) per update/query (but log n is based on
  501.     //   the coordinate range, not number of elements).
  502.     // -----------------------------------------------------------------
  503.     // Constraints:
  504.     //   - n can be as large as 1e9 (or even more, if memory allows).
  505.     //   - Number of updates should not be too large (e.g., ≤ 1e5) to keep
  506.     //     memory reasonable.
  507.     //   - Values fit in long long.
  508.     // -----------------------------------------------------------------
  509.     // Note: The tree is implemented with a vector of nodes; each node has
  510.     //       left child, right child, and sum.  Node 0 is a null node.
  511.     // -----------------------------------------------------------------
  512.     struct Node {
  513.         ll sum;
  514.         int left, right;
  515.         Node() : sum(0), left(-1), right(-1) {}
  516.     };
  517.     vector<Node> st;
  518.     int n; // range [0, n-1]
  519.     DynamicSegTree(int n) : n(n) {
  520.         st.reserve(4 * 100000); // reserve some space
  521.         st.emplace_back(); // node 0 = null
  522.         st.emplace_back(); // node 1 = root (this was missing in the original)
  523.     }
  524.     void update(int pos, ll val) { update(1, 0, n-1, pos, val); }
  525.     void update(int node, int l, int r, int pos, ll val) {
  526.         if (l == r) {
  527.             st[node].sum = val;
  528.             return;
  529.         }
  530.         int mid = (l+r)/2;
  531.         if (pos <= mid) {
  532.             if (st[node].left == -1) {
  533.                 st[node].left = st.size();
  534.                 st.emplace_back();
  535.             }
  536.             update(st[node].left, l, mid, pos, val);
  537.         } else {
  538.             if (st[node].right == -1) {
  539.                 st[node].right = st.size();
  540.                 st.emplace_back();
  541.             }
  542.             update(st[node].right, mid+1, r, pos, val);
  543.         }
  544.         st[node].sum = (st[node].left != -1 ? st[st[node].left].sum : 0) +
  545.                        (st[node].right != -1 ? st[st[node].right].sum : 0);
  546.     }
  547.     ll query(int L, int R) { return query(1, 0, n-1, L, R); }
  548.     ll query(int node, int l, int r, int L, int R) {
  549.         if (node == -1) return 0;
  550.         if (L <= l && r <= R) return st[node].sum;
  551.         int mid = (l+r)/2;
  552.         ll res = 0;
  553.         if (L <= mid) res += query(st[node].left, l, mid, L, R);
  554.         if (R > mid) res += query(st[node].right, mid+1, r, L, R);
  555.         return res;
  556.     }
  557. };
  558.  
  559. // ---------------------------------------------------------------------
  560. // 9) Persistent Segment Tree (Chairman Tree)
  561. //    Maintains multiple versions of a segment tree after point updates.
  562. //    Often used for static range k‑th smallest queries.
  563. // ---------------------------------------------------------------------
  564.  
  565. struct PersistentSegTree {
  566.     // -----------------------------------------------------------------
  567.     // Purpose:
  568.     //   Builds a persistent segment tree (also called Chairman tree)
  569.     //   that can answer k‑th smallest queries on any subarray of a
  570.     //   static array in O(log n).
  571.     //   Each version corresponds to a prefix of the array.
  572.     // -----------------------------------------------------------------
  573.     // How to use:
  574.     //   1) Compress the array values to the range [1, m].
  575.     //   2) Create: PersistentSegTree pst(m);
  576.     //   3) pst.build(compressed_vector)  – where compressed_vector
  577.     //      contains the compressed values for the whole array.
  578.     //   4) pst.query_kth(l, r, k)        – returns the compressed value
  579.     //      of the k‑th smallest in the subarray [l, r] (both 1‑based).
  580.     //   5) Convert back using the original value array.
  581.     // -----------------------------------------------------------------
  582.     // Time Complexity: O(log m) per query.
  583.     //   Build: O(n log m).
  584.     // -----------------------------------------------------------------
  585.     // Constraints:
  586.     //   - Array size n and value range m up to ~1e5.
  587.     //   - Memory: O(n log m) nodes, reserve enough.
  588.     //   - l and r are 1‑based positions in the original array.
  589.     // -----------------------------------------------------------------
  590.     // Note: The class stores roots for each prefix.  roots[0] = empty tree.
  591.     //       query_kth(l, r, k) uses roots[l-1] and roots[r].
  592.     // -----------------------------------------------------------------
  593.     struct Node {
  594.         int left, right, sum;
  595.         Node(int l=0, int r=0, int s=0) : left(l), right(r), sum(s) {}
  596.     };
  597.     vector<Node> tree;
  598.     vector<int> roots;
  599.     int n; // range of values (1..n)
  600.     PersistentSegTree(int n) : n(n) {
  601.         tree.reserve( (n+5) * 20 );
  602.         tree.emplace_back(0,0,0); // node 0 = null
  603.         roots.push_back(0);
  604.     }
  605.     int update(int prev, int l, int r, int pos) {
  606.         int cur = tree.size();
  607.         tree.push_back(tree[prev]);
  608.         tree[cur].sum++;
  609.         if (l != r) {
  610.             int mid = (l+r)/2;
  611.             if (pos <= mid) {
  612.                 int newLeft = update(tree[prev].left, l, mid, pos);
  613.                 tree[cur].left = newLeft;
  614.             } else {
  615.                 int newRight = update(tree[prev].right, mid+1, r, pos);
  616.                 tree[cur].right = newRight;
  617.             }
  618.         }
  619.         return cur;
  620.     }
  621.     void build(const vector<int>& arr) {
  622.         for (int val : arr) {
  623.             int newRoot = update(roots.back(), 1, n, val);
  624.             roots.push_back(newRoot);
  625.         }
  626.     }
  627.     int query_kth(int l, int r, int k) {
  628.         return query_kth(roots[l-1], roots[r], 1, n, k);
  629.     }
  630.     int query_kth(int u, int v, int l, int r, int k) {
  631.         if (l == r) return l;
  632.         int mid = (l+r)/2;
  633.         int leftCount = tree[tree[v].left].sum - tree[tree[u].left].sum;
  634.         if (leftCount >= k)
  635.             return query_kth(tree[u].left, tree[v].left, l, mid, k);
  636.         else
  637.             return query_kth(tree[u].right, tree[v].right, mid+1, r, k - leftCount);
  638.     }
  639. };
  640.  
  641. // ---------------------------------------------------------------------
  642. // 10) Segment Tree Beats (incomplete – NOT IMPLEMENTED)
  643. //     This was meant to support range chmin, chmax, add, sum, etc.
  644. //     However, the original code is incomplete and contains syntax errors.
  645. //     I have removed it to avoid confusion.
  646. //     If you need a working Segment Tree Beats, please look for a
  647. //     complete implementation elsewhere.
  648. // ---------------------------------------------------------------------
  649.  
  650. // ---------------------------------------------------------------------
  651. // 11) Lazy Segment Tree for Range Affine Transformations
  652. //     Applies transformations of the form: a[i] = a[i] * mul + add
  653. //     on a range, and supports range sum queries.
  654. // ---------------------------------------------------------------------
  655.  
  656. struct LazyAffine {
  657.     // -----------------------------------------------------------------
  658.     // Purpose:
  659.     //   Maintains an array and supports range updates of the form
  660.     //     for each i in [l, r]: a[i] = a[i] * m + a
  661.     //   (where m and a are given constants) and also range sum queries.
  662.     //   This is a combination of multiplication and addition (affine).
  663.     // -----------------------------------------------------------------
  664.     // How to use:
  665.     //   1) Create: LazyAffine la(my_vector);
  666.     //   2) la.range_affine(l, r, mul, add) – applies transformation
  667.     //   3) la.range_sum(l, r)              – returns sum on [l, r]
  668.     //   Indices are 0‑based, inclusive.
  669.     // -----------------------------------------------------------------
  670.     // Time Complexity: O(log n) per operation.
  671.     // Constraints:
  672.     //   - Values fit in long long.
  673.     //   - The operations are applied in the order: first multiply then add.
  674.     //   - The lazy tags compose correctly.
  675.     // -----------------------------------------------------------------
  676.     // Note: This implementation only maintains the sum; it does not
  677.     //       maintain min/max.  For more advanced queries, extend it.
  678.     // -----------------------------------------------------------------
  679.     int n;
  680.     vector<ll> sum, mul, add;
  681.     LazyAffine(const vector<ll>& a) {
  682.         n = a.size();
  683.         sum.assign(4*n, 0);
  684.         mul.assign(4*n, 1);
  685.         add.assign(4*n, 0);
  686.         build(1, 0, n-1, a);
  687.     }
  688.     void build(int node, int l, int r, const vector<ll>& a) {
  689.         if (l == r) { sum[node] = a[l]; return; }
  690.         int mid = (l+r)/2;
  691.         build(node*2, l, mid, a);
  692.         build(node*2+1, mid+1, r, a);
  693.         sum[node] = sum[node*2] + sum[node*2+1];
  694.     }
  695.     void apply(int node, int l, int r, ll m, ll a) {
  696.         sum[node] = sum[node] * m + a * (r - l + 1);
  697.         mul[node] *= m;
  698.         add[node] = add[node] * m + a;
  699.     }
  700.     void push(int node, int l, int r) {
  701.         if (mul[node] != 1 || add[node] != 0) {
  702.             int mid = (l+r)/2;
  703.             apply(node*2, l, mid, mul[node], add[node]);
  704.             apply(node*2+1, mid+1, r, mul[node], add[node]);
  705.             mul[node] = 1; add[node] = 0;
  706.         }
  707.     }
  708.     void range_affine(int L, int R, ll m, ll a) {
  709.         range_affine(1, 0, n-1, L, R, m, a);
  710.     }
  711.     void range_affine(int node, int l, int r, int L, int R, ll m, ll a) {
  712.         if (L > r || R < l) return;
  713.         if (L <= l && r <= R) {
  714.             apply(node, l, r, m, a);
  715.             return;
  716.         }
  717.         push(node, l, r);
  718.         int mid = (l+r)/2;
  719.         range_affine(node*2, l, mid, L, R, m, a);
  720.         range_affine(node*2+1, mid+1, r, L, R, m, a);
  721.         sum[node] = sum[node*2] + sum[node*2+1];
  722.     }
  723.     ll range_sum(int L, int R) {
  724.         return range_sum(1, 0, n-1, L, R);
  725.     }
  726.     ll range_sum(int node, int l, int r, int L, int R) {
  727.         if (L > r || R < l) return 0;
  728.         if (L <= l && r <= R) return sum[node];
  729.         push(node, l, r);
  730.         int mid = (l+r)/2;
  731.         return range_sum(node*2, l, mid, L, R) +
  732.                range_sum(node*2+1, mid+1, r, L, R);
  733.     }
  734. };
  735.  
  736. // =====================================================================
  737. // Additional notes on common tricks (not code):
  738. //   - Use a segment tree to find the first index where prefix sum >= K
  739. //     by traversing the tree.
  740. //   - For 2D queries, you can use a Fenwick tree of Fenwick trees or
  741. //     a segment tree of vectors.
  742. //   - For maximum subarray sum, store total, max prefix, max suffix,
  743. //     and max subarray.
  744. //   - Offline queries can be handled by segment tree over time.
  745. // =====================================================================
  746.  
  747. // ---------------------------------------------------------------------
  748. // Example usage in main()
  749. // ---------------------------------------------------------------------
  750.  
  751. int main() {
  752.     ios::sync_with_stdio(false);
  753.     cin.tie(nullptr);
  754.  
  755.     // Example: basic sum segtree
  756.     vector<ll> arr = {1, 2, 3, 4, 5};
  757.     SegTreeSum st(arr);
  758.     cout << st.query(1, 3) << '\n'; // 2+3+4 = 9
  759.     st.update(2, 10); // arr[2] = 10
  760.     cout << st.query(1, 3) << '\n'; // 2+10+4 = 16
  761.  
  762.     // Example: lazy add + sum
  763.     LazySegTreeSum lazy(arr);
  764.     lazy.range_add(1, 3, 5); // add 5 to indices 1..3
  765.     cout << lazy.range_sum(0, 4) << '\n'; // sum all = 1+7+8+9+5 = 30
  766.  
  767.     // Example: merge sort tree
  768.     vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6};
  769.     MergeSortTree mst(a);
  770.     cout << mst.query_le(1, 5, 4) << '\n'; // in subarray [1,4,1,5,9] count <=4 => 3 (1,4,1)
  771.     cout << mst.query_kth(1, 5, 3) << '\n'; // 3rd smallest in that range -> sorted: 1,1,4,5,9 => 4
  772.  
  773.     // Example: persistent segment tree (k-th smallest in subarray)
  774.     vector<int> vals = {3, 1, 4, 1, 5, 9, 2, 6};
  775.     vector<int> comp = vals;
  776.     sort(comp.begin(), comp.end());
  777.     comp.erase(unique(comp.begin(), comp.end()), comp.end());
  778.     vector<int> compressed;
  779.     for (int x : vals) {
  780.         compressed.push_back(lower_bound(comp.begin(), comp.end(), x) - comp.begin() + 1);
  781.     }
  782.     PersistentSegTree pst(comp.size());
  783.     pst.build(compressed);
  784.     // k-th smallest in range [l, r] (1‑based positions)
  785.     cout << comp[pst.query_kth(2, 5, 2) - 1] << '\n'; // subarray indices 1..4 (0-based) => vals[1..4] = {1,4,1,5}, 2nd smallest = 1
  786.  
  787.     return 0;
  788. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
9
16
30
3
4
1
https://ideone.com/VNGdoY
language:
C++ (gcc 8.3)
created:
1 day 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!