fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // ===================================================================
  5. // This file contains a collection of 2D Segment Tree algorithms.
  6. // Each function/class is ready to be used as a "black box".
  7. // Read the comments above each one to understand:
  8. //   - What it solves
  9. //   - What input it expects
  10. //   - What it returns
  11. //   - Time complexity
  12. //   - Important constraints / assumptions
  13. //   - Any extra notes
  14. // ===================================================================
  15.  
  16. // ===================================================================
  17. // 1) STATIC 2D SEGMENT TREE FOR SUM
  18. //    (Point Update, Rectangle Sum Query)
  19. // ===================================================================
  20.  
  21. // -------------------------------------------------------------------
  22. // CLASS: SegTree2DSum
  23. // -------------------------------------------------------------------
  24. // WHAT IT DOES:
  25. //   Builds a 2D segment tree over a grid of integers (N rows x M columns).
  26. //   It supports:
  27. //     - Point update: add a value (delta) to a single cell.
  28. //     - Rectangle sum: compute the sum of all cells inside a given
  29. //       rectangle [x1..x2] × [y1..y2].
  30. //
  31. // INPUT:
  32. //   - The grid is given as a 2D vector (N x M) in the `build` function.
  33. //   - Coordinates are 0‑based (row and column indices start from 0).
  34. //
  35. // OUTPUT:
  36. //   - `querySum` returns an integer – the sum of the rectangle.
  37. //   - `updatePoint` does not return anything; it modifies the tree.
  38. //
  39. // TIME COMPLEXITY:
  40. //   - Build: O(N * M)  (actually O(4*N * 4*M) but practically O(N*M)).
  41. //   - Update: O(log N * log M).
  42. //   - Query:  O(log N * log M).
  43. //
  44. // MEMORY:
  45. //   - O(N * M)  (stored as a 2D array of size 4*N × 4*M).
  46. //
  47. // CONSTRAINTS / ASSUMPTIONS:
  48. //   - N and M must be known at construction time.
  49. //   - The grid values are integers (int).
  50. //   - The grid size (N × M) should be reasonable (e.g., N, M <= 1000)
  51. //     because memory grows quadratically.
  52. //   - Updates add a delta; they do not set a value (use negative delta
  53. //     to subtract).
  54. //
  55. // NOTES:
  56. //   - This implementation uses 0‑based indices everywhere.
  57. //   - It is a "static" tree because the grid size is fixed after build.
  58. //   - The class allocates a full 4*N × 4*M array, so it may be heavy
  59. //     for large grids.
  60. //   - If you need to handle sparse data or very large coordinates,
  61. //     see the Fenwick2D class below (coordinate compression).
  62. // -------------------------------------------------------------------
  63.  
  64. class SegTree2DSum {
  65.     int n, m;
  66.     vector<vector<int>> tree;  // tree[4*n][4*m]
  67.  
  68.     // Build the column segment tree for a single row (leaf row node).
  69.     void buildColTree(int rowNode, int colNode, int l, int r, const vector<int>& row) {
  70.         if (l == r) {
  71.             tree[rowNode][colNode] = row[l];
  72.             return;
  73.         }
  74.         int mid = (l + r) / 2;
  75.         buildColTree(rowNode, colNode*2, l, mid, row);
  76.         buildColTree(rowNode, colNode*2+1, mid+1, r, row);
  77.         tree[rowNode][colNode] = tree[rowNode][colNode*2] + tree[rowNode][colNode*2+1];
  78.     }
  79.  
  80.     // Merge the column trees of two child row nodes into the parent row node.
  81.     void mergeColTrees(int rowNode, int colNode, int l, int r) {
  82.         if (l == r) {
  83.             tree[rowNode][colNode] = tree[rowNode*2][colNode] + tree[rowNode*2+1][colNode];
  84.             return;
  85.         }
  86.         int mid = (l + r) / 2;
  87.         mergeColTrees(rowNode, colNode*2, l, mid);
  88.         mergeColTrees(rowNode, colNode*2+1, mid+1, r);
  89.         tree[rowNode][colNode] = tree[rowNode*2][colNode] + tree[rowNode*2+1][colNode];
  90.     }
  91.  
  92.     // Build the row segment tree recursively.
  93.     void buildRow(int node, int l, int r, const vector<vector<int>>& grid) {
  94.         if (l == r) {
  95.             // Leaf row: build its column tree from the grid row.
  96.             buildColTree(node, 1, 0, m-1, grid[l]);
  97.             return;
  98.         }
  99.         int mid = (l + r) / 2;
  100.         buildRow(node*2, l, mid, grid);
  101.         buildRow(node*2+1, mid+1, r, grid);
  102.         // Merge the column trees of the two children.
  103.         mergeColTrees(node, 1, 0, m-1);
  104.     }
  105.  
  106.     // Update a single column in a leaf row node.
  107.     void updateCol(int rowNode, int colNode, int l, int r, int y, int delta) {
  108.         if (l == r) {
  109.             tree[rowNode][colNode] += delta;
  110.             return;
  111.         }
  112.         int mid = (l + r) / 2;
  113.         if (y <= mid) updateCol(rowNode, colNode*2, l, mid, y, delta);
  114.         else updateCol(rowNode, colNode*2+1, mid+1, r, y, delta);
  115.         tree[rowNode][colNode] = tree[rowNode][colNode*2] + tree[rowNode][colNode*2+1];
  116.     }
  117.  
  118.     // After updating one child row, recompute the current row node's
  119.     // column tree for the affected column.
  120.     void updateColMerge(int rowNode, int colNode, int l, int r, int y, int delta) {
  121.         if (l == r) {
  122.             tree[rowNode][colNode] = tree[rowNode*2][colNode] + tree[rowNode*2+1][colNode];
  123.             return;
  124.         }
  125.         int mid = (l + r) / 2;
  126.         if (y <= mid) updateColMerge(rowNode, colNode*2, l, mid, y, delta);
  127.         else updateColMerge(rowNode, colNode*2+1, mid+1, r, y, delta);
  128.         tree[rowNode][colNode] = tree[rowNode*2][colNode] + tree[rowNode*2+1][colNode];
  129.     }
  130.  
  131.     // Update a cell (x,y) by adding delta, traversing the row tree.
  132.     void updateRow(int node, int l, int r, int x, int y, int delta) {
  133.         if (l == r) {
  134.             updateCol(node, 1, 0, m-1, y, delta);
  135.             return;
  136.         }
  137.         int mid = (l + r) / 2;
  138.         if (x <= mid) updateRow(node*2, l, mid, x, y, delta);
  139.         else updateRow(node*2+1, mid+1, r, x, y, delta);
  140.         // After child is updated, update the current node's column tree.
  141.         updateColMerge(node, 1, 0, m-1, y, delta);
  142.     }
  143.  
  144.     // Query the column tree of a given row node for a range of columns.
  145.     int queryCol(int rowNode, int colNode, int l, int r, int y1, int y2) {
  146.         if (y1 <= l && r <= y2) {
  147.             return tree[rowNode][colNode];
  148.         }
  149.         int mid = (l + r) / 2;
  150.         int res = 0;
  151.         if (y1 <= mid) res += queryCol(rowNode, colNode*2, l, mid, y1, y2);
  152.         if (y2 > mid) res += queryCol(rowNode, colNode*2+1, mid+1, r, y1, y2);
  153.         return res;
  154.     }
  155.  
  156.     // Query the row tree for a rectangle [x1..x2] × [y1..y2].
  157.     int queryRow(int node, int l, int r, int x1, int x2, int y1, int y2) {
  158.         if (x1 <= l && r <= x2) {
  159.             return queryCol(node, 1, 0, m-1, y1, y2);
  160.         }
  161.         int mid = (l + r) / 2;
  162.         int res = 0;
  163.         if (x1 <= mid) res += queryRow(node*2, l, mid, x1, x2, y1, y2);
  164.         if (x2 > mid) res += queryRow(node*2+1, mid+1, r, x1, x2, y1, y2);
  165.         return res;
  166.     }
  167.  
  168. public:
  169.     // Constructor: prepares the tree with given dimensions.
  170.     // Input: number of rows (n) and columns (m).
  171.     SegTree2DSum(int n, int m) : n(n), m(m) {
  172.         tree.assign(4*n, vector<int>(4*m, 0));
  173.     }
  174.  
  175.     // Build the 2D segment tree from the grid.
  176.     // Input: a 2D vector grid of size n x m (must match the constructor dimensions).
  177.     // Time: O(n*m).
  178.     void build(const vector<vector<int>>& grid) {
  179.         buildRow(1, 0, n-1, grid);
  180.     }
  181.  
  182.     // Point update: add 'delta' to cell (x,y).
  183.     // Input: x (row), y (column), delta (value to add, can be negative).
  184.     // Time: O(log n * log m).
  185.     void updatePoint(int x, int y, int delta) {
  186.         updateRow(1, 0, n-1, x, y, delta);
  187.     }
  188.  
  189.     // Rectangle sum query: sum of cells in [x1..x2] × [y1..y2].
  190.     // Input: x1, y1, x2, y2 (all 0‑based indices, inclusive).
  191.     // Returns: the sum as an integer.
  192.     // Time: O(log n * log m).
  193.     int querySum(int x1, int y1, int x2, int y2) {
  194.         return queryRow(1, 0, n-1, x1, x2, y1, y2);
  195.     }
  196. };
  197.  
  198. // ===================================================================
  199. // 2) STATIC 2D SEGMENT TREE FOR MIN / MAX
  200. //    (Point Update, Rectangle Query)
  201. // ===================================================================
  202.  
  203. // -------------------------------------------------------------------
  204. // CLASS: SegTree2DMinMax
  205. // -------------------------------------------------------------------
  206. // WHAT IT DOES:
  207. //   Same structure as the sum version, but instead of summing,
  208. //   it combines values using a custom merge function (e.g., min or max).
  209. //   It supports point updates (set a cell to a value) and rectangle
  210. //   queries (get the min or max over a rectangle).
  211. //
  212. // INPUT:
  213. //   - Template parameter T: the data type (e.g., int, long long).
  214. //   - Template parameter mergeFunc: a function pointer T (*)(T,T) that
  215. //     combines two values (e.g., minFunc or maxFunc).
  216. //   - The constructor also takes an 'identity' value – the neutral element
  217. //     for the merge operation (e.g., INF for min, -INF for max).
  218. //   - The grid is given as a 2D vector of T.
  219. //   - Coordinates are 0‑based.
  220. //
  221. // OUTPUT:
  222. //   - `query` returns a value of type T – the result of the merge over
  223. //     the rectangle (min or max).
  224. //   - `updatePoint` sets a cell to a new value (not an addition).
  225. //
  226. // TIME COMPLEXITY:
  227. //   - Build: O(N * M).
  228. //   - Update: O(log N * log M).
  229. //   - Query:  O(log N * log M).
  230. //
  231. // MEMORY:
  232. //   - O(N * M).
  233. //
  234. // CONSTRAINTS / ASSUMPTIONS:
  235. //   - N and M must be known at construction.
  236. //   - The grid values and the identity must be of type T.
  237. //   - The merge function must be associative (like min, max).
  238. //   - Use INT_MAX / INT_MIN for int, or LLONG_MAX / LLONG_MIN for long long.
  239. //   - Point update sets the cell to the given value (overwrites).
  240. //
  241. // NOTES:
  242. //   - The class is generic, so you need to instantiate it with a merge
  243. //     function. Two helper functions (minFunc, maxFunc) are provided below.
  244. //   - Example usage: SegTree2DMinMax<int, minFunc> segMin(n, m, INT_MAX);
  245. //   - Because it's a static tree, it allocates full memory; use only for
  246. //     moderate grid sizes.
  247. // -------------------------------------------------------------------
  248.  
  249. template<typename T, T (*mergeFunc)(T, T)>
  250. class SegTree2DMinMax {
  251.     int n, m;
  252.     vector<vector<T>> tree;
  253.     T identity;
  254.  
  255.     // Build column tree for a single row.
  256.     void buildColTree(int rowNode, int colNode, int l, int r, const vector<T>& row) {
  257.         if (l == r) {
  258.             tree[rowNode][colNode] = row[l];
  259.             return;
  260.         }
  261.         int mid = (l + r) / 2;
  262.         buildColTree(rowNode, colNode*2, l, mid, row);
  263.         buildColTree(rowNode, colNode*2+1, mid+1, r, row);
  264.         tree[rowNode][colNode] = mergeFunc(tree[rowNode][colNode*2], tree[rowNode][colNode*2+1]);
  265.     }
  266.  
  267.     // Merge two child row nodes' column trees into the parent.
  268.     void mergeColTrees(int rowNode, int colNode, int l, int r) {
  269.         if (l == r) {
  270.             tree[rowNode][colNode] = mergeFunc(tree[rowNode*2][colNode], tree[rowNode*2+1][colNode]);
  271.             return;
  272.         }
  273.         int mid = (l + r) / 2;
  274.         mergeColTrees(rowNode, colNode*2, l, mid);
  275.         mergeColTrees(rowNode, colNode*2+1, mid+1, r);
  276.         tree[rowNode][colNode] = mergeFunc(tree[rowNode*2][colNode], tree[rowNode*2+1][colNode]);
  277.     }
  278.  
  279.     void buildRow(int node, int l, int r, const vector<vector<T>>& grid) {
  280.         if (l == r) {
  281.             buildColTree(node, 1, 0, m-1, grid[l]);
  282.             return;
  283.         }
  284.         int mid = (l + r) / 2;
  285.         buildRow(node*2, l, mid, grid);
  286.         buildRow(node*2+1, mid+1, r, grid);
  287.         mergeColTrees(node, 1, 0, m-1);
  288.     }
  289.  
  290.     void updateCol(int rowNode, int colNode, int l, int r, int y, T val) {
  291.         if (l == r) {
  292.             tree[rowNode][colNode] = val;
  293.             return;
  294.         }
  295.         int mid = (l + r) / 2;
  296.         if (y <= mid) updateCol(rowNode, colNode*2, l, mid, y, val);
  297.         else updateCol(rowNode, colNode*2+1, mid+1, r, y, val);
  298.         tree[rowNode][colNode] = mergeFunc(tree[rowNode][colNode*2], tree[rowNode][colNode*2+1]);
  299.     }
  300.  
  301.     // Recompute current row node's column tree after a child row update.
  302.     void updateColMerge(int rowNode, int colNode, int l, int r, int y, T val) {
  303.         if (l == r) {
  304.             tree[rowNode][colNode] = mergeFunc(tree[rowNode*2][colNode], tree[rowNode*2+1][colNode]);
  305.             return;
  306.         }
  307.         int mid = (l + r) / 2;
  308.         if (y <= mid) updateColMerge(rowNode, colNode*2, l, mid, y, val);
  309.         else updateColMerge(rowNode, colNode*2+1, mid+1, r, y, val);
  310.         tree[rowNode][colNode] = mergeFunc(tree[rowNode*2][colNode], tree[rowNode*2+1][colNode]);
  311.     }
  312.  
  313.     void updateRow(int node, int l, int r, int x, int y, T val) {
  314.         if (l == r) {
  315.             updateCol(node, 1, 0, m-1, y, val);
  316.             return;
  317.         }
  318.         int mid = (l + r) / 2;
  319.         if (x <= mid) updateRow(node*2, l, mid, x, y, val);
  320.         else updateRow(node*2+1, mid+1, r, x, y, val);
  321.         updateColMerge(node, 1, 0, m-1, y, val);
  322.     }
  323.  
  324.     T queryCol(int rowNode, int colNode, int l, int r, int y1, int y2) {
  325.         if (y1 <= l && r <= y2) {
  326.             return tree[rowNode][colNode];
  327.         }
  328.         int mid = (l + r) / 2;
  329.         T res = identity;
  330.         if (y1 <= mid) res = mergeFunc(res, queryCol(rowNode, colNode*2, l, mid, y1, y2));
  331.         if (y2 > mid) res = mergeFunc(res, queryCol(rowNode, colNode*2+1, mid+1, r, y1, y2));
  332.         return res;
  333.     }
  334.  
  335.     T queryRow(int node, int l, int r, int x1, int x2, int y1, int y2) {
  336.         if (x1 <= l && r <= x2) {
  337.             return queryCol(node, 1, 0, m-1, y1, y2);
  338.         }
  339.         int mid = (l + r) / 2;
  340.         T res = identity;
  341.         if (x1 <= mid) res = mergeFunc(res, queryRow(node*2, l, mid, x1, x2, y1, y2));
  342.         if (x2 > mid) res = mergeFunc(res, queryRow(node*2+1, mid+1, r, x1, x2, y1, y2));
  343.         return res;
  344.     }
  345.  
  346. public:
  347.     // Constructor: pass grid dimensions and the identity value for the merge.
  348.     // Input: n (rows), m (columns), identity (e.g., INF for min, -INF for max).
  349.     SegTree2DMinMax(int n, int m, T identity) : n(n), m(m), identity(identity) {
  350.         tree.assign(4*n, vector<T>(4*m, identity));
  351.     }
  352.  
  353.     // Build the tree from the grid.
  354.     // Input: 2D vector grid of size n x m.
  355.     // Time: O(n*m).
  356.     void build(const vector<vector<T>>& grid) {
  357.         buildRow(1, 0, n-1, grid);
  358.     }
  359.  
  360.     // Point update: set cell (x,y) to value 'val' (overwrites previous value).
  361.     // Input: x, y, val.
  362.     // Time: O(log n * log m).
  363.     void updatePoint(int x, int y, T val) {
  364.         updateRow(1, 0, n-1, x, y, val);
  365.     }
  366.  
  367.     // Rectangle query: returns the merge result over [x1..x2] × [y1..y2].
  368.     // Input: x1, y1, x2, y2 (inclusive, 0‑based).
  369.     // Returns: the min or max (depending on mergeFunc) as type T.
  370.     // Time: O(log n * log m).
  371.     T query(int x1, int y1, int x2, int y2) {
  372.         return queryRow(1, 0, n-1, x1, x2, y1, y2);
  373.     }
  374. };
  375.  
  376. // -------------------------------------------------------------------
  377. // Helper merge functions for min and max (to use with SegTree2DMinMax)
  378. // -------------------------------------------------------------------
  379. // minFunc: returns the smaller of two values.
  380. // maxFunc: returns the larger of two values.
  381. // These are simple functions that you can pass as template arguments.
  382. int minFunc(int a, int b) { return min(a, b); }
  383. int maxFunc(int a, int b) { return max(a, b); }
  384.  
  385. // ===================================================================
  386. // 3) 2D FENWICK TREE WITH COORDINATE COMPRESSION (SPARSE POINTS)
  387. //    (Point Update, Prefix Sum, Rectangle Sum)
  388. // ===================================================================
  389.  
  390. // -------------------------------------------------------------------
  391. // CLASS: Fenwick2D
  392. // -------------------------------------------------------------------
  393. // WHAT IT DOES:
  394. //   This is a 2D Fenwick tree (also called Binary Indexed Tree) that
  395. //   works with sparse points. It is useful when the grid is huge
  396. //   (coordinates up to 1e9) but the number of points that will ever
  397. //   be updated is relatively small (K points).
  398. //   It supports:
  399. //     - Point update: add a value (delta) to a point (x, y).
  400. //     - Prefix sum: sum of all points with X <= x and Y <= y.
  401. //     - Rectangle sum: sum over a rectangle using inclusion‑exclusion
  402. //       from prefix sums.
  403. //
  404. // INPUT:
  405. //   - Constructor: a list of all points (x, y) that will ever be updated.
  406. //     This is used to compress the coordinates.
  407. //   - Updates and queries use the same coordinate values (they must be
  408. //     among those initially provided, otherwise the update will fail
  409. //     or produce wrong results).
  410. //   - Coordinates can be negative or large; they are stored as ints.
  411. //
  412. // OUTPUT:
  413. //   - `add` modifies the internal structure (no return).
  414. //   - `prefixSum(x, y)` returns the sum of points with X <= x and Y <= y.
  415. //   - `rectangleSum(x1, y1, x2, y2)` returns the sum in that rectangle.
  416. //
  417. // TIME COMPLEXITY:
  418. //   - Build (constructor): O(K log K) roughly, where K is the number of
  419. //     unique points (or the number of points provided).
  420. //   - Update: O(log K) in both dimensions.
  421. //   - Prefix sum: O(log K) in both dimensions.
  422. //
  423. // MEMORY:
  424. //   - O(K log K) in the worst case, because each point is inserted into
  425. //     O(log K) Fenwick nodes. In practice, it is manageable for K up to
  426. //     a few hundred thousand.
  427. //
  428. // CONSTRAINTS / ASSUMPTIONS:
  429. //   - All points that will be updated must be passed to the constructor
  430. //     beforehand. If you try to update a point that was not in the list,
  431. //     the internal `ys` vector for that x will not contain that y, and
  432. //     the update will access out‑of‑bounds (or silently fail).
  433. //   - Coordinates are integer values.
  434. //   - The class uses 1‑based indexing internally for the Fenwick tree,
  435. //     but the public interface uses the original coordinates (0‑based or
  436. //     any integer).
  437. //   - Rectangle queries use the standard inclusion‑exclusion formula
  438. //     with prefix sums.
  439. //
  440. // NOTES:
  441. //   - "Fenwick tree" is a data structure that efficiently supports
  442. //     prefix sums and point updates. It is also called a Binary Indexed
  443. //     Tree (BIT).
  444. //   - "Coordinate compression" means we map large coordinate values to
  445. //     small indices (1..K) so that we can store arrays of manageable size.
  446. //   - This implementation is offline: it needs all update points in
  447. //     advance. If you have dynamic additions of new points, you need a
  448. //     different approach (e.g., a dynamic 2D segment tree).
  449. //   - The `prefixSum` method returns the sum for all points with X <= x
  450. //     and Y <= y. If x or y is smaller than all provided coordinates,
  451. //     it returns 0.
  452. // -------------------------------------------------------------------
  453.  
  454. class Fenwick2D {
  455.     int n; // number of compressed x coordinates
  456.     vector<vector<int>> ys; // compressed y coordinates per x node
  457.     vector<vector<int>> bit; // BIT values (2D)
  458.     vector<int> xs; // all unique x coordinates
  459.  
  460. public:
  461.     // Constructor: takes a list of all points that will ever be updated.
  462.     // Input: vector of pairs (x, y). Duplicates are allowed (they are handled).
  463.     // Time: O(K log K) where K is the number of points.
  464.     Fenwick2D(const vector<pair<int,int>>& points) {
  465.         // Collect all unique x coordinates.
  466.         vector<int> allX;
  467.         for (auto &p : points) allX.push_back(p.first);
  468.         sort(allX.begin(), allX.end());
  469.         allX.erase(unique(allX.begin(), allX.end()), allX.end());
  470.         xs = allX;
  471.         n = xs.size();
  472.         ys.resize(n+1);
  473.         // For each point, add its y to all Fenwick nodes that cover its x.
  474.         for (auto &p : points) {
  475.             int x = p.first;
  476.             int idx = lower_bound(xs.begin(), xs.end(), x) - xs.begin() + 1; // 1-indexed
  477.             for (int i = idx; i <= n; i += i & -i) {
  478.                 ys[i].push_back(p.second);
  479.             }
  480.         }
  481.         // Compress each y list and allocate the BIT array.
  482.         bit.resize(n+1);
  483.         for (int i = 1; i <= n; i++) {
  484.             sort(ys[i].begin(), ys[i].end());
  485.             ys[i].erase(unique(ys[i].begin(), ys[i].end()), ys[i].end());
  486.             bit[i].assign(ys[i].size()+1, 0);
  487.         }
  488.     }
  489.  
  490.     // Point update: add 'delta' to point (x, y).
  491.     // Input: x, y (coordinates), delta (value to add).
  492.     // Time: O(log K) where K is the number of points.
  493.     // IMPORTANT: (x,y) must have been included in the constructor's point list.
  494.     void add(int x, int y, int delta) {
  495.         int xi = lower_bound(xs.begin(), xs.end(), x) - xs.begin() + 1;
  496.         for (int i = xi; i <= n; i += i & -i) {
  497.             int yi = lower_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin() + 1;
  498.             for (int j = yi; j < (int)bit[i].size(); j += j & -j) {
  499.                 bit[i][j] += delta;
  500.             }
  501.         }
  502.     }
  503.  
  504.     // Prefix sum: sum of all points with X <= x and Y <= y.
  505.     // Input: x, y (coordinates).
  506.     // Returns: integer sum.
  507.     // Time: O(log K).
  508.     int prefixSum(int x, int y) {
  509.         int xi = upper_bound(xs.begin(), xs.end(), x) - xs.begin(); // number of xs <= x
  510.         int res = 0;
  511.         for (int i = xi; i > 0; i -= i & -i) {
  512.             int yi = upper_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin();
  513.             for (int j = yi; j > 0; j -= j & -j) {
  514.                 res += bit[i][j];
  515.             }
  516.         }
  517.         return res;
  518.     }
  519.  
  520.     // Rectangle sum: sum of points inside [x1..x2] × [y1..y2].
  521.     // Input: x1, y1, x2, y2 (inclusive, any order).
  522.     // Returns: integer sum.
  523.     // Time: O(log K) (four prefixSum calls).
  524.     int rectangleSum(int x1, int y1, int x2, int y2) {
  525.         return prefixSum(x2, y2) - prefixSum(x1-1, y2) - prefixSum(x2, y1-1) + prefixSum(x1-1, y1-1);
  526.     }
  527. };
  528.  
  529. // ===================================================================
  530. // 4) 2D SEGMENT TREE WITH LAZY PROPAGATION (RANGE UPDATES)
  531. //    (Concept only – not implemented)
  532. // ===================================================================
  533. // This section is kept as a placeholder. Lazy propagation in 2D is
  534. // advanced and rarely needed. For most problems, a 2D BIT or offline
  535. // sweepline is sufficient. No implementation is provided here.
  536. // ===================================================================
  537.  
  538. // ===================================================================
  539. // 5) COMMON TRICKS & PATTERNS FOR ECPC/ACPC
  540. // ===================================================================
  541. // The following notes are for your reference:
  542. //
  543. // 5.1) Offline queries with sweepline:
  544. //      For static 2D points, you can answer rectangle sum queries by
  545. //      sorting points by x, queries by x2, and using a 1D BIT on y.
  546. //      This avoids 2D segment trees entirely.
  547. //
  548. // 5.2) Dynamic 2D Segment Tree using pointers:
  549. //      When the grid is huge and updates/queries are few, you can
  550. //      create nodes on demand. This is not implemented here because
  551. //      it is complex; the Fenwick2D class is usually enough for sparse data.
  552. //
  553. // 5.3) Using 2D Segment Tree for range maximum with point updates:
  554. //      The SegTree2DMinMax class above does exactly that.
  555. //
  556. // 5.4) Combining with Binary Search on answer:
  557. //      If you need to find the smallest rectangle containing a certain
  558. //      number of points, you can binary search the size and use a
  559. //      2D segment tree to count points in a rectangle.
  560. //
  561. // 5.5) Negative coordinates or large ranges:
  562. //      Always use coordinate compression (Fenwick2D) for such cases.
  563. // ===================================================================
  564.  
  565. // ===================================================================
  566. // 6) SPARSE 2D SEGMENT TREE (DYNAMIC ALLOCATION) – NOT IMPLEMENTED
  567. // ===================================================================
  568. // A fully dynamic 2D segment tree would allocate nodes only when
  569. // needed. Because of its complexity, we recommend using Fenwick2D
  570. // with coordinate compression instead.
  571. // ===================================================================
  572.  
  573. // ===================================================================
  574. // 7) EXAMPLE USAGE
  575. // ===================================================================
  576. // The main() function below demonstrates how to use the three main
  577. // classes. Read the comments inside to see each step.
  578. // ===================================================================
  579.  
  580. int main() {
  581.     ios::sync_with_stdio(false);
  582.     cin.tie(nullptr);
  583.  
  584.     // ---------- Example 1: Sum 2D Segment Tree ----------
  585.     vector<vector<int>> grid = {
  586.         {1, 2, 3},
  587.         {4, 5, 6},
  588.         {7, 8, 9}
  589.     };
  590.     int n = 3, m = 3;
  591.     SegTree2DSum seg(n, m);
  592.     seg.build(grid);
  593.  
  594.     cout << "Sum of entire grid: " << seg.querySum(0,0,2,2) << '\n'; // 45
  595.     cout << "Sum of subrectangle (1,1)-(2,2): " << seg.querySum(1,1,2,2) << '\n'; // 5+6+8+9=28
  596.  
  597.     seg.updatePoint(1,1, 10); // add 10 to cell (1,1) which was 5 -> now 15
  598.     cout << "After update, sum of subrectangle (1,1)-(2,2): " << seg.querySum(1,1,2,2) << '\n'; // 15+6+8+9=38
  599.  
  600.     // ---------- Example 2: Min 2D Segment Tree ----------
  601.     SegTree2DMinMax<int, minFunc> segMin(n, m, INT_MAX);
  602.     segMin.build(grid);
  603.     cout << "Min in entire grid: " << segMin.query(0,0,2,2) << '\n'; // 1
  604.     segMin.updatePoint(0,0, 0); // set (0,0) to 0
  605.     cout << "Min after update: " << segMin.query(0,0,2,2) << '\n'; // 0
  606.  
  607.     // ---------- Example 3: 2D Fenwick with coordinate compression ----------
  608.     vector<pair<int,int>> points = {{1,1}, {2,3}, {5,7}};
  609.     Fenwick2D fw(points);
  610.     fw.add(1,1, 5);
  611.     fw.add(2,3, 10);
  612.     cout << "Prefix sum up to (2,3): " << fw.prefixSum(2,3) << '\n'; // 15
  613.     cout << "Prefix sum up to (5,7): " << fw.prefixSum(5,7) << '\n'; // 15
  614.     fw.add(5,7, 3);
  615.     cout << "After add: " << fw.prefixSum(5,7) << '\n'; // 18
  616.  
  617.     return 0;
  618. }
  619.  
  620. // ===================================================================
  621. // ADDITIONAL NOTES FOR ECPC/ACPC COMPETITORS:
  622. // - 2D Segment Trees are memory heavy; use them only when N and M are
  623. //   small (<= 1000) or when coordinates are compressed.
  624. // - For dynamic updates and large coordinates, prefer Fenwick2D with
  625. //   compression (offline).
  626. // - For offline static queries, a sweepline + 1D BIT is often simpler
  627. //   and faster.
  628. // - When implementing your own 2D segment tree, watch out for recursion
  629. //   depth and memory consumption.
  630. // - Always test edge cases: N=1, M=1, empty rectangles, negative
  631. //   coordinates (Fenwick2D handles them if you provide them).
  632. // ===================================================================
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Sum of entire grid: 45
Sum of subrectangle (1,1)-(2,2): 28
After update, sum of subrectangle (1,1)-(2,2): 38
Min in entire grid: 1
Min after update: 0
Prefix sum up to (2,3): 15
Prefix sum up to (5,7): 15
After add: 18
https://ideone.com/CwrRzq
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!