peltorator

2D Down Segment Tree Point Update

May 19th, 2021
657
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct SegmentTree2D {
  6.     static const int N = 1000, M = 1000;
  7.     int n, m;
  8.     long long tree[2 * N][2 * M];
  9.  
  10.     void build(const vector<vector<int>>& arr) {
  11.         n = arr.size();
  12.         m = arr[0].size();
  13.         for (int i = 2 * n - 1; i > 0; i--) {
  14.             for (int j = 2 * m - 1; j > 0; j--) {
  15.                 if (i < n) {
  16.                     tree[i][j] = tree[2 * i][j] + tree[2 * i + 1][j];
  17.                 } else if (j < m) {
  18.                     tree[i][j] = tree[i][2 * j] + tree[i][2 * j + 1];
  19.                 } else {
  20.                     tree[i][j] = arr[i - n][j - m];
  21.                 }
  22.             }
  23.         }
  24.     }
  25.  
  26.     void updatePoint(int x, int y, int newVal) {
  27.         x += n;
  28.         y += m;
  29.         int curx = x;
  30.         while (curx > 0) {
  31.             int cury = y;
  32.             while (cury > 0) {
  33.                 if (curx < n) {
  34.                     tree[curx][cury] = tree[2 * curx][cury] + tree[2 * curx + 1][cury];
  35.                 } else if (cury < m) {
  36.                     tree[curx][cury] = tree[curx][2 * cury] + tree[curx][2 * cury + 1];
  37.                 } else {
  38.                     tree[curx][cury] = newVal;
  39.                 }
  40.                 cury >>= 1;
  41.             }
  42.             curx >>= 1;
  43.         }
  44.     }
  45.  
  46.     long long findSum(int lx, int rx, int ly, int ry) { // [lx, rx) * [ly, ry)
  47.         lx += n;
  48.         rx += n;
  49.  
  50.         long long ans = 0;
  51.         while (lx < rx) {
  52.             int curly = ly + m;
  53.             int curry = ry + m;
  54.             while (curly < curry) {
  55.                 if (curly & 1) {
  56.                     if (lx & 1) {
  57.                         ans += tree[lx][curly];
  58.                     }
  59.                     if (rx & 1) {
  60.                         ans += tree[rx - 1][curly];
  61.                     }
  62.                 }
  63.                 if (curry & 1) {
  64.                     if (lx & 1) {
  65.                         ans += tree[lx][curry - 1];
  66.                     }
  67.                     if (rx & 1) {
  68.                         ans += tree[rx - 1][curry - 1];
  69.                     }
  70.                 }
  71.                 curly = (curly + 1) >> 1;
  72.                 curry >>= 1;
  73.             }
  74.             lx = (lx + 1) >> 1;
  75.             rx >>= 1;
  76.         }
  77.         return ans;
  78.     }
  79. } segTree;
  80.  
  81. int main() {
  82.     int n, m;
  83.     cin >> n >> m;
  84.     vector<vector<int>> arr(n, vector<int>(m));
  85.     for (int i = 0; i < n; i++) {
  86.         for (int j = 0; j < m; j++) {
  87.             cin >> arr[i][j];
  88.         }
  89.     }
  90.     segTree.build(arr);
  91.  
  92.     int q;
  93.     cin >> q;
  94.     for (int i = 0; i < q; i++) {
  95.         int type;
  96.         cin >> type;
  97.         if (type == 1) {
  98.             int x, y, newVal;
  99.             cin >> x >> y >> newVal;
  100.             segTree.updatePoint(x - 1, y - 1, newVal);
  101.         } else {
  102.             int lx, rx, ly, ry;
  103.             cin >> lx >> rx >> ly >> ry;
  104.             cout << segTree.findSum(lx - 1, rx, ly - 1, ry) << '\n';
  105.         }
  106.     }
  107. }
RAW Paste Data