乱七八糟的笔记（没有原理……）

前言

因为loceaner太菜了，他什么东西都不会
所以他打算学一个东西就记录一下
不过因为他很菜，所以他不会写原理……
而且，他希望在2019CSP之前不会断更
就酱紫，就是写给他自己的……因为他太菜了

二维前缀和

//知识点:二维前缀和
/*
By:Loceaner
*/
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

inline int read() {
    char c = getchar();
    int x = 0, f = 1;
    for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
    return x * f;
}

const int N = 1000;

int n, m;
int a[N][N], b[N][N];

int main() {
    n = read(), m = read();
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            a[i][j] = read();
            b[i][j] = a[i][j] + b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
        }
    }
    for(int i, u1, v1, u2, v2; i <= m; i++) {
        u1 = read(), v1 = read(), u2 = read(), v2 = read();
        cout << b[u2][v2] - b[u1 - 1][v2] - b[u2][v1 - 1] + b[u1 - 1][v1 - 1] << '\n';
    }
    return 0;
}

二维差分：二维差分

//知识点:
/*
By:Loceaner
*/
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

inline int read() {
    char c = getchar();
    int x = 0, f = 1;
    for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
    return x * f;
}

const int N = 1e3 + 11;

int n, m, a[N][N];

int main() {
    n = read(), m = read();
    for(int i = 1, u1, u2, v1, v2; i <= m; i++) {
        u1 = read(), v1 = read(), u2 = read(), v2 = read();
        a[u1][v1] += 1;
        a[u2 + 1][v2 + 1] += 1;
        a[u2 + 1][v1] -= 1;
        a[u1][v2 + 1] -= 1;
    }
    //C[x1][y1] += x ,  C[x2 + 1][y2 + 1] += x ,  C[x1][y2 + 1] -= x , C[x2 + 1][y1] -= x;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            a[i][j] = a[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];;
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cout << a[i][j] << ' ';
        }
        cout << '\n';
    }
    return 0;
}