fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // ================================================================
  5. // GENERAL NOTES FOR ALL DATA STRUCTURES:
  6. // - All indices are 1‑based unless explicitly stated otherwise.
  7. // - Use 'long long' for sums to avoid overflow.
  8. // - The term "BIT" stands for Binary Indexed Tree (Fenwick Tree).
  9. // - "Prefix sum" means sum over rectangle [1..x] × [1..y].
  10. // - "Sweep line" is an offline technique where events are processed in order of one coordinate.
  11. // - "Coordinate compression" replaces large coordinate values with smaller indices to save memory.
  12. // - Some structures are "offline", meaning all updates/queries must be known beforehand.
  13. // ================================================================
  14.  
  15. // ================================================================
  16. // 1) Fenwick2D – Basic 2D BIT for Point Update & Rectangle Sum Query
  17. // ================================================================
  18. /**
  19.  * Fenwick2D – 2D Binary Indexed Tree for point updates and prefix/rectangle sum queries.
  20.  *
  21.  * PURPOSE:
  22.  * Maintains a 2D grid of numbers. Supports adding a value to a single cell and
  23.  * querying the sum of any axis‑aligned rectangle.
  24.  *
  25.  * USAGE:
  26.  *   Fenwick2D fw(n, m);          // n rows, m columns (1‑based indexing)
  27.  *   fw.add(x, y, delta);         // add 'delta' to cell (x, y)
  28.  *   long long s = fw.sum(x, y);  // sum of rectangle [1..x] × [1..y]
  29.  *   long long rect = fw.query(x1, y1, x2, y2); // sum of [x1..x2] × [y1..y2]
  30.  *   fw.clear();                  // reset all values to zero (O(n*m))
  31.  *
  32.  * TIME COMPLEXITY:
  33.  *   add, sum, query: O(log n * log m)
  34.  *   clear: O(n * m)
  35.  *
  36.  * CONSTRAINTS / NOTES:
  37.  *   - n, m can be up to ~2000 for a dense BIT; larger grids should use sparse or offline methods.
  38.  *   - Indices must be in [1..n] and [1..m].
  39.  *   - The BIT is initially zero; add initial values manually.
  40.  *   - clear() is expensive; avoid frequent calls on large grids.
  41.  */
  42. struct Fenwick2D {
  43.     int n, m;
  44.     vector<vector<long long>> bit;
  45.  
  46.     Fenwick2D() {}
  47.     Fenwick2D(int n_, int m_) { init(n_, m_); }
  48.  
  49.     void init(int n_, int m_) {
  50.         n = n_;
  51.         m = m_;
  52.         bit.assign(n + 2, vector<long long>(m + 2, 0));
  53.     }
  54.  
  55.     void add(int x, int y, long long delta) {
  56.         for (int i = x; i <= n; i += i & -i)
  57.             for (int j = y; j <= m; j += j & -j)
  58.                 bit[i][j] += delta;
  59.     }
  60.  
  61.     long long sum(int x, int y) const {
  62.         long long res = 0;
  63.         for (int i = x; i > 0; i -= i & -i)
  64.             for (int j = y; j > 0; j -= j & -j)
  65.                 res += bit[i][j];
  66.         return res;
  67.     }
  68.  
  69.     long long query(int x1, int y1, int x2, int y2) const {
  70.         return sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1);
  71.     }
  72.  
  73.     void clear() {
  74.         for (int i = 1; i <= n; ++i)
  75.             fill(bit[i].begin(), bit[i].end(), 0);
  76.     }
  77. };
  78.  
  79. // ================================================================
  80. // 2) RangeUpdatePointQuery2D – Range Add + Point Query via Difference BIT
  81. // ================================================================
  82. /**
  83.  * RangeUpdatePointQuery2D – Supports adding a value to a whole rectangle and
  84.  * then querying the value at a single point (offline or online).
  85.  *
  86.  * PURPOSE:
  87.  * Uses a 2D difference array implemented with a BIT to perform range additions
  88.  * and point queries efficiently.
  89.  *
  90.  * USAGE:
  91.  *   RangeUpdatePointQuery2D ru(n, m);
  92.  *   ru.rangeAdd(x1, y1, x2, y2, val);  // add 'val' to all cells in that rectangle
  93.  *   long long v = ru.pointQuery(x, y);  // get the current value at cell (x, y)
  94.  *
  95.  * TIME COMPLEXITY:
  96.  *   rangeAdd: O(log n * log m)  (calls four point updates)
  97.  *   pointQuery: O(log n * log m)
  98.  *
  99.  * NOTES:
  100.  *   - All indices are 1‑based.
  101.  *   - The BIT is used as a difference array; point queries retrieve the accumulated value.
  102.  *   - No need to initialize with base values; treat base values as separate updates.
  103.  *   - Extra space (n+2, m+2) is allocated to avoid out‑of‑bounds when updating at x2+1 etc.
  104.  */
  105. struct RangeUpdatePointQuery2D {
  106.     int n, m;
  107.     Fenwick2D diff;
  108.  
  109.     RangeUpdatePointQuery2D(int n_, int m_) {
  110.         n = n_;
  111.         m = m_;
  112.         diff.init(n + 2, m + 2);
  113.     }
  114.  
  115.     void rangeAdd(int x1, int y1, int x2, int y2, long long val) {
  116.         diff.add(x1, y1, val);
  117.         diff.add(x2 + 1, y1, -val);
  118.         diff.add(x1, y2 + 1, -val);
  119.         diff.add(x2 + 1, y2 + 1, val);
  120.     }
  121.  
  122.     long long pointQuery(int x, int y) {
  123.         return diff.sum(x, y);
  124.     }
  125. };
  126.  
  127. // ================================================================
  128. // 3) RangeUpdateRangeQuery2D – Range Add + Range Sum (using four BITs)
  129. // ================================================================
  130. /**
  131.  * RangeUpdateRangeQuery2D – Supports adding a value to any rectangle and
  132.  * querying the sum of any rectangle.
  133.  *
  134.  * PURPOSE:
  135.  * Uses four difference BITs to maintain the 2D array so that both range updates
  136.  * and range queries are supported in O(log n * log m).
  137.  *
  138.  * USAGE:
  139.  *   RangeUpdateRangeQuery2D rurq(n, m);
  140.  *   rurq.rangeAdd(x1, y1, x2, y2, val);  // add val to all cells in rectangle
  141.  *   long long s = rurq.query(x1, y1, x2, y2); // sum of that rectangle
  142.  *
  143.  * TIME COMPLEXITY:
  144.  *   rangeAdd: O(log n * log m)
  145.  *   query: O(log n * log m)
  146.  *
  147.  * NOTES:
  148.  *   - Works with 1‑based indices.
  149.  *   - Internally stores four BITs; memory is 4 * n * m (may be large).
  150.  *   - Values and sums are long long.
  151.  *   - The formula used: prefixSum(x,y) = B1*x*y - B2*y - B3*x + B4
  152.  *     where B1..B4 are the BITs storing difference components.
  153.  */
  154. struct RangeUpdateRangeQuery2D {
  155.     int n, m;
  156.     Fenwick2D B1, B2, B3, B4;
  157.  
  158.     RangeUpdateRangeQuery2D(int n_, int m_) {
  159.         n = n_;
  160.         m = m_;
  161.         B1.init(n + 2, m + 2);
  162.         B2.init(n + 2, m + 2);
  163.         B3.init(n + 2, m + 2);
  164.         B4.init(n + 2, m + 2);
  165.     }
  166.  
  167.     void _pointAdd(int x, int y, long long val) {
  168.         B1.add(x, y, val);
  169.         B2.add(x, y, val * (x - 1));
  170.         B3.add(x, y, val * (y - 1));
  171.         B4.add(x, y, val * (x - 1) * (y - 1));
  172.     }
  173.  
  174.     void rangeAdd(int x1, int y1, int x2, int y2, long long val) {
  175.         _pointAdd(x1, y1, val);
  176.         _pointAdd(x2 + 1, y1, -val);
  177.         _pointAdd(x1, y2 + 1, -val);
  178.         _pointAdd(x2 + 1, y2 + 1, val);
  179.     }
  180.  
  181.     long long prefixSum(int x, int y) {
  182.         long long s1 = B1.sum(x, y) * x * y;
  183.         long long s2 = B2.sum(x, y) * y;
  184.         long long s3 = B3.sum(x, y) * x;
  185.         long long s4 = B4.sum(x, y);
  186.         return s1 - s2 - s3 + s4;
  187.     }
  188.  
  189.     long long query(int x1, int y1, int x2, int y2) {
  190.         return prefixSum(x2, y2) - prefixSum(x1 - 1, y2)
  191.              - prefixSum(x2, y1 - 1) + prefixSum(x1 - 1, y1 - 1);
  192.     }
  193. };
  194.  
  195. // ================================================================
  196. // 4) SparseFenwick2D (Compressed) – Sparse 2D BIT with Coordinate Compression
  197. // ================================================================
  198. /**
  199.  * SparseFenwick2D – Sparse 2D BIT for large coordinates, using offline compression.
  200.  *
  201.  * PURPOSE:
  202.  * When the grid is huge (coordinates up to 1e9) but the number of points is small,
  203.  * this structure compresses coordinates and builds a sparse BIT to save memory.
  204.  * Supports point updates and rectangle sum queries.
  205.  *
  206.  * USAGE (Offline):
  207.  *   1. Collect all (x,y) points that will ever be updated or queried.
  208.  *   2. Build the structure: SparseFenwick2D sfw(coords);  // coords: vector<pair<int,int>>
  209.  *   3. Add values: sfw.add(x, y, delta);
  210.  *   4. Query: sfw.query(x1, y1, x2, y2)  // sum in rectangle
  211.  *
  212.  * TIME COMPLEXITY:
  213.  *   build: O(P log P) where P = number of distinct points.
  214.  *   add: O(log N * log K) where N = number of distinct x, K = average y per x-node.
  215.  *   query: same as add.
  216.  *
  217.  * CONSTRAINTS / NOTES:
  218.  *   - All coordinates must be known beforehand (offline).
  219.  *   - Use 'long long' for sums.
  220.  *   - The class internally uses unordered_map for fast x‑index lookup.
  221.  *   - Only points that appear in the input 'coords' can be updated/queried.
  222.  *   - Queries with x1-1 or y1-1 are handled automatically if those coordinates are included.
  223.  *     If a queried x does not exist in the compressed list, the sum is safely returned as 0.
  224.  *   - Build time and memory are proportional to number of points.
  225.  */
  226. struct SparseFenwick2D {
  227.     int n;
  228.     vector<vector<int>> xs;
  229.     vector<vector<long long>> bit;
  230.     unordered_map<int,int> xIndex;
  231.  
  232.     SparseFenwick2D() {}
  233.  
  234.     SparseFenwick2D(const vector<pair<int,int>>& coords) {
  235.         build(coords);
  236.     }
  237.  
  238.     void build(const vector<pair<int,int>>& coords) {
  239.         vector<int> allX;
  240.         for (auto &p : coords) allX.push_back(p.first);
  241.         sort(allX.begin(), allX.end());
  242.         allX.erase(unique(allX.begin(), allX.end()), allX.end());
  243.         n = allX.size();
  244.  
  245.         xs.assign(n + 1, {});
  246.         for (auto &p : coords) {
  247.             int x = p.first;
  248.             int idx = lower_bound(allX.begin(), allX.end(), x) - allX.begin() + 1;
  249.             for (int i = idx; i <= n; i += i & -i) {
  250.                 xs[i].push_back(p.second);
  251.             }
  252.         }
  253.         bit.assign(n + 1, {});
  254.         for (int i = 1; i <= n; ++i) {
  255.             sort(xs[i].begin(), xs[i].end());
  256.             xs[i].erase(unique(xs[i].begin(), xs[i].end()), xs[i].end());
  257.             bit[i].assign(xs[i].size() + 1, 0);
  258.         }
  259.         xIndex.clear();
  260.         for (int i = 0; i < (int)allX.size(); ++i)
  261.             xIndex[allX[i]] = i + 1;
  262.     }
  263.  
  264.     void add(int x, int y, long long delta) {
  265.         int idx = xIndex[x]; // x must be present in the built map
  266.         for (int i = idx; i <= n; i += i & -i) {
  267.             int pos = lower_bound(xs[i].begin(), xs[i].end(), y) - xs[i].begin() + 1;
  268.             for (int j = pos; j < (int)bit[i].size(); j += j & -j)
  269.                 bit[i][j] += delta;
  270.         }
  271.     }
  272.  
  273.     long long sum(int x, int y) {
  274.         auto it = xIndex.find(x);
  275.         if (it == xIndex.end()) return 0;   // x not present in compressed list -> prefix sum is 0
  276.         int idx = it->second;
  277.         long long res = 0;
  278.         for (int i = idx; i > 0; i -= i & -i) {
  279.             int pos = upper_bound(xs[i].begin(), xs[i].end(), y) - xs[i].begin();
  280.             for (int j = pos; j > 0; j -= j & -j)
  281.                 res += bit[i][j];
  282.         }
  283.         return res;
  284.     }
  285.  
  286.     long long query(int x1, int y1, int x2, int y2) {
  287.         return sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1);
  288.     }
  289. };
  290.  
  291. // ================================================================
  292. // 5) Fenwick1D – Basic 1D BIT (for reference and offline methods)
  293. // ================================================================
  294. /**
  295.  * Fenwick1D – Standard 1D Binary Indexed Tree for point update and prefix sum.
  296.  *
  297.  * PURPOSE:
  298.  * Supports adding a value at a position and querying prefix sum.
  299.  *
  300.  * USAGE:
  301.  *   Fenwick1D bit(N);         // 1‑based indices up to N
  302.  *   bit.add(idx, val);        // add 'val' at index idx
  303.  *   int s = bit.sum(idx);     // sum of [1..idx]
  304.  *   int range = bit.rangeSum(l, r); // sum of [l..r]
  305.  *
  306.  * TIME COMPLEXITY:
  307.  *   add, sum, rangeSum: O(log N)
  308.  *
  309.  * NOTES:
  310.  *   - Used as a helper in offline sweep‑line algorithms.
  311.  *   - All values are integers; cast to long long if needed.
  312.  */
  313. struct Fenwick1D {
  314.     int n;
  315.     vector<int> bit;
  316.     Fenwick1D(int n) : n(n), bit(n + 1, 0) {}
  317.     void add(int idx, int val) {
  318.         for (; idx <= n; idx += idx & -idx) bit[idx] += val;
  319.     }
  320.     int sum(int idx) {
  321.         int res = 0;
  322.         for (; idx > 0; idx -= idx & -idx) res += bit[idx];
  323.         return res;
  324.     }
  325.     int rangeSum(int l, int r) {
  326.         if (l > r) return 0;
  327.         return sum(r) - sum(l - 1);
  328.     }
  329. };
  330.  
  331. // ================================================================
  332. // 6) solveOffline – Count Points in Rectangles (Offline, no updates)
  333. // ================================================================
  334. /**
  335.  * solveOffline – Counts the number of points inside each query rectangle.
  336.  *
  337.  * PURPOSE:
  338.  * Given a set of static points and many rectangle queries, this function returns
  339.  * for each query the number of points that lie inside the rectangle.
  340.  * It uses a sweep line on x‑coordinate and a 1D BIT on y‑coordinate.
  341.  *
  342.  * USAGE:
  343.  *   vector<Point> points;                // each has (x, y)
  344.  *   vector<tuple<int,int,int,int>> rectQueries; // each: (x1, y1, x2, y2)
  345.  *   vector<int> ans = solveOffline(n, m, points, rectQueries);
  346.  *   // ans[i] = number of points in the i‑th rectangle.
  347.  *
  348.  * PARAMETERS:
  349.  *   n, m – not actually used (can be ignored), they are the grid bounds.
  350.  *   points – list of points (1‑based coordinates).
  351.  *   rectQueries – each tuple holds (x1, y1, x2, y2) inclusive.
  352.  *
  353.  * RETURN:
  354.  *   vector<int> containing answers in the same order as queries.
  355.  *
  356.  * TIME COMPLEXITY:
  357.  *   O((P + Q) log Y) where P = number of points, Q = number of queries,
  358.  *   Y = number of distinct y‑coordinates.
  359.  *
  360.  * NOTES:
  361.  *   - All coordinates are 1‑based.
  362.  *   - The function compresses y‑coordinates automatically.
  363.  *   - The grid bounds (n,m) are ignored; they are only for reference.
  364.  *   - The points are static; no updates are allowed.
  365.  *   - Uses inclusion‑exclusion to turn each rectangle query into 4 prefix queries.
  366.  */
  367. struct Point {
  368.     int x, y;
  369. };
  370.  
  371. struct Query {
  372.     int x, y, idx, sign;
  373. };
  374.  
  375. vector<int> solveOffline(int n, int m, vector<Point>& points, vector<tuple<int,int,int,int>>& rectQueries) {
  376.     vector<int> allY;
  377.     for (auto &p : points) allY.push_back(p.y);
  378.     for (auto &[x1, y1, x2, y2] : rectQueries) {
  379.         allY.push_back(y1 - 1);
  380.         allY.push_back(y2);
  381.     }
  382.     sort(allY.begin(), allY.end());
  383.     allY.erase(unique(allY.begin(), allY.end()), allY.end());
  384.  
  385.     auto getY = [&](int y) { return lower_bound(allY.begin(), allY.end(), y) - allY.begin() + 1; };
  386.  
  387.     vector<tuple<int, int, int, int>> events;
  388.     for (auto &p : points) {
  389.         events.push_back({p.x, getY(p.y), -1, 0});
  390.     }
  391.  
  392.     int q = rectQueries.size();
  393.     vector<int> ans(q, 0);
  394.     for (int i = 0; i < q; i++) {
  395.         auto [x1, y1, x2, y2] = rectQueries[i];
  396.         events.push_back({x2, getY(y2), i, 1});
  397.         events.push_back({x1 - 1, getY(y2), i, -1});
  398.         events.push_back({x2, getY(y1 - 1), i, -1});
  399.         events.push_back({x1 - 1, getY(y1 - 1), i, 1});
  400.     }
  401.  
  402.     sort(events.begin(), events.end());
  403.     Fenwick1D bit(allY.size() + 5);
  404.  
  405.     for (auto &[x, y, idx, sign] : events) {
  406.         if (idx == -1) {
  407.             bit.add(y, 1);
  408.         } else {
  409.             ans[idx] += sign * bit.sum(y);
  410.         }
  411.     }
  412.     return ans;
  413. }
  414.  
  415. // ================================================================
  416. // 7) SparseFenwick2D (unordered_map) – Sparse 2D BIT using hash maps
  417. // ================================================================
  418. /**
  419.  * SparseFenwick2D (with unordered_map) – Another sparse 2D BIT that uses hash maps
  420.  * to store only updated cells.
  421.  *
  422.  * PURPOSE:
  423.  * Similar to the compressed sparse version but does not require offline coordinate
  424.  * compression. It stores a hash map for each BIT node mapping y -> accumulated value.
  425.  * Suitable when the number of updates is small but coordinates can be arbitrary.
  426.  *
  427.  * USAGE:
  428.  *   SparseFenwick2D sfw(maxX);   // maxX is the maximum x‑coordinate (1‑based)
  429.  *   sfw.add(x, y, delta);
  430.  *   long long s = sfw.sum(x, y);
  431.  *   long long rect = sfw.query(x1, y1, x2, y2);
  432.  *
  433.  * TIME COMPLEXITY:
  434.  *   add: O(log X * average hash map insert)
  435.  *   sum: O(log X * average hash map lookup)
  436.  *   query: same as sum (4 calls).
  437.  *
  438.  * NOTES:
  439.  *   - The first dimension (x) must be within [1..maxX] (maxX given in constructor).
  440.  *   - Uses unordered_map for each BIT node; memory usage is O(number of updated points * log X).
  441.  *   - Hash map overhead may be high; prefer the compressed version if coordinates are known.
  442.  *   - All indices are 1‑based.
  443.  */
  444. struct SparseFenwick2D_hash {  // renamed to avoid duplicate name
  445.     int n;
  446.     vector<unordered_map<int, long long>> bit;
  447.  
  448.     SparseFenwick2D_hash(int n) : n(n), bit(n + 1) {}
  449.  
  450.     void add(int x, int y, long long delta) {
  451.         for (int i = x; i <= n; i += i & -i) {
  452.             bit[i][y] += delta;
  453.         }
  454.     }
  455.  
  456.     long long sum(int x, int y) {
  457.         long long res = 0;
  458.         for (int i = x; i > 0; i -= i & -i) {
  459.             auto it = bit[i].find(y);
  460.             if (it != bit[i].end()) res += it->second;
  461.         }
  462.         return res;
  463.     }
  464.  
  465.     long long query(int x1, int y1, int x2, int y2) {
  466.         return sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1);
  467.     }
  468. };
  469.  
  470. // ================================================================
  471. // 8) Fenwick2DMax – 2D BIT for Max (only non‑decreasing updates)
  472. // ================================================================
  473. /**
  474.  * Fenwick2DMax – 2D BIT that supports point updates with 'max' operation
  475.  * and prefix maximum queries.
  476.  *
  477.  * PURPOSE:
  478.  * Maintains a grid where each cell holds a value. Supports updating a cell with a
  479.  * new value (only if it is larger) and querying the maximum value in the prefix
  480.  * rectangle [1..x] × [1..y]. This works correctly only when updates are non‑decreasing.
  481.  *
  482.  * USAGE:
  483.  *   Fenwick2DMax fw(n, m);
  484.  *   fw.update(x, y, val);  // sets bit[i][j] = max(bit[i][j], val) for all ancestors
  485.  *   int maxVal = fw.query(x, y); // maximum value in [1..x] × [1..y]
  486.  *
  487.  * TIME COMPLEXITY:
  488.  *   update: O(log n * log m)
  489.  *   query: O(log n * log m)
  490.  *
  491.  * NOTES:
  492.  *   - The BIT initially holds 0. If values can be negative, adjust initial value.
  493.  *   - Updates must be non‑decreasing (i.e., val should be >= previous values at that cell,
  494.  *     otherwise the max property breaks). Use only when you insert values in increasing order.
  495.  *   - Works for 1‑based indices.
  496.  */
  497. struct Fenwick2DMax {
  498.     int n, m;
  499.     vector<vector<int>> bit;
  500.  
  501.     Fenwick2DMax(int n, int m) : n(n), m(m), bit(n + 1, vector<int>(m + 1, 0)) {}
  502.  
  503.     void update(int x, int y, int val) {
  504.         for (int i = x; i <= n; i += i & -i)
  505.             for (int j = y; j <= m; j += j & -j)
  506.                 bit[i][j] = max(bit[i][j], val);
  507.     }
  508.  
  509.     int query(int x, int y) {
  510.         int res = 0;
  511.         for (int i = x; i > 0; i -= i & -i)
  512.             for (int j = y; j > 0; j -= j & -j)
  513.                 res = max(res, bit[i][j]);
  514.         return res;
  515.     }
  516. };
  517.  
  518. // ================================================================
  519. // 9) Fenwick3D – 3D BIT for Point Update and Cuboid Sum Query
  520. // ================================================================
  521. /**
  522.  * Fenwick3D – 3D Binary Indexed Tree for point updates and cuboid sum queries.
  523.  *
  524.  * PURPOSE:
  525.  * Extends the 2D BIT to three dimensions. Supports adding a value to a point (x,y,z)
  526.  * and querying the sum of the box [1..x] × [1..y] × [1..z].
  527.  *
  528.  * USAGE:
  529.  *   Fenwick3D fw(n, m, k);       // dimensions: x=1..n, y=1..m, z=1..k
  530.  *   fw.add(x, y, z, delta);
  531.  *   long long s = fw.sum(x, y, z);
  532.  *   long long box = fw.cuboidSum(x1,y1,z1, x2,y2,z2); // sum inside the box
  533.  *
  534.  * TIME COMPLEXITY:
  535.  *   add, sum: O(log n * log m * log k)
  536.  *   cuboidSum: O(log n * log m * log k) (8 calls to sum)
  537.  *
  538.  * NOTES:
  539.  *   - All indices are 1‑based.
  540.  *   - Memory is n*m*k; use only for small dimensions (e.g., up to 100 each).
  541.  *   - Use long long for sums.
  542.  *   - Inclusion‑exclusion in 3D has 8 terms.
  543.  */
  544. struct Fenwick3D {
  545.     int n, m, k;
  546.     vector<vector<vector<long long>>> bit;
  547.  
  548.     Fenwick3D(int n, int m, int k) : n(n), m(m), k(k),
  549.         bit(n + 1, vector<vector<long long>>(m + 1, vector<long long>(k + 1, 0))) {}
  550.  
  551.     void add(int x, int y, int z, long long delta) {
  552.         for (int i = x; i <= n; i += i & -i)
  553.             for (int j = y; j <= m; j += j & -j)
  554.                 for (int l = z; l <= k; l += l & -l)
  555.                     bit[i][j][l] += delta;
  556.     }
  557.  
  558.     long long sum(int x, int y, int z) {
  559.         long long res = 0;
  560.         for (int i = x; i > 0; i -= i & -i)
  561.             for (int j = y; j > 0; j -= j & -j)
  562.                 for (int l = z; l > 0; l -= l & -l)
  563.                     res += bit[i][j][l];
  564.         return res;
  565.     }
  566.  
  567.     long long cuboidSum(int x1, int y1, int z1, int x2, int y2, int z2) {
  568.         return sum(x2, y2, z2)
  569.              - sum(x1 - 1, y2, z2) - sum(x2, y1 - 1, z2) - sum(x2, y2, z1 - 1)
  570.              + sum(x1 - 1, y1 - 1, z2) + sum(x1 - 1, y2, z1 - 1) + sum(x2, y1 - 1, z1 - 1)
  571.              - sum(x1 - 1, y1 - 1, z1 - 1);
  572.     }
  573. };
  574.  
  575. // ================================================================
  576. // 10) BIT1D – Another 1D BIT (helper for offline methods)
  577. // ================================================================
  578. /**
  579.  * BIT1D – Simple 1D Fenwick Tree for sum with long long values.
  580.  *
  581.  * PURPOSE:
  582.  * Same as Fenwick1D but with long long support. Used in offline sweep‑line solutions.
  583.  *
  584.  * USAGE:
  585.  *   BIT1D bit(N);
  586.  *   bit.add(idx, val);
  587.  *   long long s = bit.sum(idx);
  588.  *   long long range = bit.rangeSum(l, r);
  589.  *
  590.  * TIME COMPLEXITY:
  591.  *   O(log N) per operation.
  592.  *
  593.  * NOTES:
  594.  *   - 1‑based indices.
  595.  *   - Internally uses long long to avoid overflow.
  596.  */
  597. struct BIT1D {
  598.     int n;
  599.     vector<long long> bit;
  600.     BIT1D(int n = 0) { init(n); }
  601.     void init(int n_) { n = n_; bit.assign(n + 1, 0); }
  602.     void add(int idx, long long val) {
  603.         for (; idx <= n; idx += idx & -idx) bit[idx] += val;
  604.     }
  605.     long long sum(int idx) {
  606.         long long res = 0;
  607.         for (; idx > 0; idx -= idx & -idx) res += bit[idx];
  608.         return res;
  609.     }
  610.     long long rangeSum(int l, int r) {
  611.         if (l > r) return 0;
  612.         return sum(r) - sum(l - 1);
  613.     }
  614. };
  615.  
  616. // ================================================================
  617. // 11) offlineRectSumWithUpdates – Offline Rectangle Sum with Point Updates
  618. // ================================================================
  619. /**
  620.  * offlineRectSumWithUpdates – Solves rectangle sum queries with point updates offline.
  621.  *
  622.  * PURPOSE:
  623.  * Given a set of initial points, point updates (add delta to a point), and rectangle sum
  624.  * queries, this function computes the answer for each query efficiently using a sweep line
  625.  * over x‑coordinate and a 1D BIT over y‑coordinate.
  626.  *
  627.  * USAGE:
  628.  *   vector<pair<int,int>> points;                    // initial points (x,y)
  629.  *   vector<tuple<int,int,long long>> pointUpdates;   // (x, y, delta)
  630.  *   vector<tuple<int,int,int,int>> rectQueries;      // (x1, y1, x2, y2)
  631.  *   vector<long long> ans = offlineRectSumWithUpdates(points, pointUpdates, rectQueries);
  632.  *
  633.  * RETURN:
  634.  *   vector<long long> where ans[i] is the sum of all point values inside the i‑th rectangle.
  635.  *
  636.  * TIME COMPLEXITY:
  637.  *   O((P + U + Q) log Y) where P = #initial points, U = #updates, Q = #queries,
  638.  *   Y = number of distinct y‑coordinates after compression.
  639.  *
  640.  * NOTES:
  641.  *   - All coordinates are 1‑based.
  642.  *   - The function compresses y‑coordinates automatically.
  643.  *   - Works offline: all updates and queries must be known in advance.
  644.  *   - Each rectangle query is transformed into 4 prefix queries using inclusion‑exclusion.
  645.  *   - Initial points are treated as updates with delta=1 (or any given value? The code adds 1 for each point.
  646.  *     If you need different values, modify the code accordingly.)
  647.  */
  648. vector<long long> offlineRectSumWithUpdates(
  649.     vector<pair<int,int>>& points,
  650.     vector<tuple<int,int,long long>>& pointUpdates,
  651.     vector<tuple<int,int,int,int>>& rectQueries
  652. ) {
  653.     // compress y
  654.     vector<int> ys;
  655.     for (auto &p : points) ys.push_back(p.second);
  656.     for (auto &[x,y,delta] : pointUpdates) ys.push_back(y);
  657.     for (auto &[x1,y1,x2,y2] : rectQueries) {
  658.         ys.push_back(y1 - 1);
  659.         ys.push_back(y2);
  660.     }
  661.     sort(ys.begin(), ys.end());
  662.     ys.erase(unique(ys.begin(), ys.end()), ys.end());
  663.     auto getY = [&](int y) { return lower_bound(ys.begin(), ys.end(), y) - ys.begin() + 1; };
  664.  
  665.     struct Event {
  666.         int x, y, id, sign, type; // type=0: point, type=1: query
  667.         long long val;
  668.         bool operator<(const Event& o) const {
  669.             if (x != o.x) return x < o.x;
  670.             return type < o.type;
  671.         }
  672.     };
  673.     vector<Event> events;
  674.  
  675.     for (auto &p : points) {
  676.         events.push_back({p.first, getY(p.second), -1, 0, 0, 1});
  677.     }
  678.     for (auto &[x,y,delta] : pointUpdates) {
  679.         events.push_back({x, getY(y), -1, 0, 0, delta});
  680.     }
  681.  
  682.     int q = rectQueries.size();
  683.     vector<long long> ans(q, 0);
  684.     for (int i = 0; i < q; i++) {
  685.         auto &[x1,y1,x2,y2] = rectQueries[i];
  686.         events.push_back({x2, getY(y2), i, 1, 1, 0});
  687.         events.push_back({x1 - 1, getY(y2), i, -1, 1, 0});
  688.         events.push_back({x2, getY(y1 - 1), i, -1, 1, 0});
  689.         events.push_back({x1 - 1, getY(y1 - 1), i, 1, 1, 0});
  690.     }
  691.  
  692.     sort(events.begin(), events.end());
  693.     BIT1D bit(ys.size() + 5);
  694.  
  695.     for (auto &e : events) {
  696.         if (e.type == 0) {
  697.             bit.add(e.y, e.val);
  698.         } else {
  699.             ans[e.id] += e.sign * bit.sum(e.y);
  700.         }
  701.     }
  702.     return ans;
  703. }
  704.  
  705. // ================================================================
  706. // 12) FenwickXOR – 1D BIT for XOR (point update, prefix XOR)
  707. // ================================================================
  708. /**
  709.  * FenwickXOR – 1D BIT that supports point updates with XOR and prefix XOR queries.
  710.  *
  711.  * PURPOSE:
  712.  * Maintains an array of integers where you can XOR a value at a position and
  713.  * query the XOR of elements from 1 to idx.
  714.  *
  715.  * USAGE:
  716.  *   FenwickXOR fx(N);
  717.  *   fx.add(idx, val);          // bit[idx] ^= val (XOR update)
  718.  *   int x = fx.prefixXor(idx); // XOR of [1..idx]
  719.  *   int rangeXor = fx.rangeXor(l, r); // XOR of [l..r]
  720.  *
  721.  * TIME COMPLEXITY:
  722.  *   O(log N) per operation.
  723.  *
  724.  * NOTES:
  725.  *   - Works with int; for long long, change type.
  726.  *   - All indices are 1‑based.
  727.  */
  728. struct FenwickXOR {
  729.     int n;
  730.     vector<int> bit;
  731.     FenwickXOR(int n = 0) { init(n); }
  732.     void init(int n_) { n = n_; bit.assign(n + 1, 0); }
  733.  
  734.     void add(int idx, int val) {
  735.         for (; idx <= n; idx += idx & -idx) bit[idx] ^= val;
  736.     }
  737.  
  738.     int prefixXor(int idx) {
  739.         int res = 0;
  740.         for (; idx > 0; idx -= idx & -idx) res ^= bit[idx];
  741.         return res;
  742.     }
  743.  
  744.     int rangeXor(int l, int r) {
  745.         return prefixXor(r) ^ prefixXor(l - 1);
  746.     }
  747. };
  748.  
  749. // ================================================================
  750. // 13) Fenwick2DMulti – Multiple BITs for Sum and Sum of Squares
  751. // ================================================================
  752. /**
  753.  * Fenwick2DMulti – Maintains two 2D BITs to store both sum and sum of squares.
  754.  *
  755.  * PURPOSE:
  756.  * Useful when you need to compute variance or other statistics from point updates.
  757.  * Supports point updates and prefix queries for both sum and sum of squares.
  758.  *
  759.  * USAGE:
  760.  *   Fenwick2DMulti fw(n, m);
  761.  *   fw.add(x, y, val);          // add val to cell (x,y)
  762.  *   auto [s, sq] = fw.sum(x, y); // returns pair: (sum, sum of squares) for prefix [1..x][1..y]
  763.  *
  764.  * TIME COMPLEXITY:
  765.  *   add, sum: O(log n * log m)
  766.  *
  767.  * NOTES:
  768.  *   - 1‑based indices.
  769.  *   - The BIT stores sum and sum of squares separately. 
  770.  *   - Use long long for both values; squares can be large.
  771.  */
  772. struct Fenwick2DMulti {
  773.     int n, m;
  774.     vector<vector<long long>> bitSum, bitSq;
  775.  
  776.     Fenwick2DMulti(int n_, int m_) { init(n_, m_); }
  777.     void init(int n_, int m_) {
  778.         n = n_; m = m_;
  779.         bitSum.assign(n + 1, vector<long long>(m + 1, 0));
  780.         bitSq.assign(n + 1, vector<long long>(m + 1, 0));
  781.     }
  782.  
  783.     void add(int x, int y, long long val) {
  784.         long long sq = val * val;
  785.         for (int i = x; i <= n; i += i & -i)
  786.             for (int j = y; j <= m; j += j & -j) {
  787.                 bitSum[i][j] += val;
  788.                 bitSq[i][j] += sq;
  789.             }
  790.     }
  791.  
  792.     pair<long long, long long> sum(int x, int y) {
  793.         long long s = 0, sq = 0;
  794.         for (int i = x; i > 0; i -= i & -i)
  795.             for (int j = y; j > 0; j -= j & -j) {
  796.                 s += bitSum[i][j];
  797.                 sq += bitSq[i][j];
  798.             }
  799.         return {s, sq};
  800.     }
  801. };
  802.  
  803. // ================================================================
  804. // 14) Example usage in main()
  805. // ================================================================
  806. int main() {
  807.     ios::sync_with_stdio(false);
  808.     cin.tie(nullptr);
  809.  
  810.     // Example 1: Point update, rectangle sum query
  811.     int n = 5, m = 5;
  812.     Fenwick2D fw(n, m);
  813.     // initial values (if any)
  814.     for (int i = 1; i <= n; ++i) {
  815.         for (int j = 1; j <= m; ++j) {
  816.             long long val;
  817.             cin >> val; // read initial grid (1‑based)
  818.             fw.add(i, j, val);
  819.         }
  820.     }
  821.     // point update: add 10 at (3,3)
  822.     fw.add(3, 3, 10);
  823.     // query rectangle [2..4] × [2..4]
  824.     cout << fw.query(2, 2, 4, 4) << '\n';
  825.  
  826.     // Example 2: Range update, point query
  827.     RangeUpdatePointQuery2D ru(n, m);
  828.     ru.rangeAdd(2, 2, 4, 4, 5); // add 5 to rectangle
  829.     cout << ru.pointQuery(3, 3) << '\n'; // should print 5
  830.  
  831.     // Example 3: Range update, range query
  832.     RangeUpdateRangeQuery2D rurq(n, m);
  833.     rurq.rangeAdd(1, 1, 3, 3, 2);
  834.     rurq.rangeAdd(2, 2, 4, 4, -1);
  835.     cout << rurq.query(1, 1, 4, 4) << '\n';
  836.  
  837.     // Example 4: Sparse 2D BIT (compressed)
  838.     vector<pair<int,int>> coords = {{100, 200}, {100, 300}, {200, 100}, {300, 400}};
  839.     SparseFenwick2D sfw(coords);
  840.     sfw.add(100, 200, 5);
  841.     sfw.add(200, 100, 7);
  842.     // query rectangle [100..300] × [100..400]
  843.     cout << sfw.query(100, 100, 300, 400) << '\n'; // should be 12
  844.  
  845.     return 0;
  846. }
  847.  
  848. // ======================================================================
  849. // ADDITIONAL NOTES ON PERFORMANCE AND USAGE:
  850. //   - Standard 2D BIT: O(log n * log m) per operation.
  851. //   - Sparse BIT (compressed): O(log N * log K) where N = number of distinct x,
  852. //     K = average y per node, but requires offline knowledge.
  853. //   - Always prefer 1‑based indexing to avoid confusion.
  854. //   - Use long long for sums to avoid overflow.
  855. //   - For large grids (n,m up to 1e3) standard 2D BIT is fine;
  856. //     for n,m up to 1e5 use sparse or sweep line.
  857. //   - The file contains only complete, working structures. Duplicate or incomplete
  858. //     versions have been removed or clearly separated.
  859. // ======================================================================
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
846010622211418
5
9
12
https://ideone.com/MZNR9K
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!