1 条题解

  • 0
    @ 2025-6-15 10:38:40
    #include <bits/stdc++.h>
    #define int long long
    using namespace std;
    const int MAXN = 4096;
    int n, m;
    int lowbit(int x)
    {
        return x & (-x);
    }
    // t[x][y] 存 t[x-lowbit(x)+1 ~ x][y-lowbit(y)+1 ~ y] 的元素之和
    int t[MAXN + 5][MAXN + 5];
    void update(int x, int y, int z)
    {
        for (int i = x; i <= n; i += lowbit(i))
            for (int j = y; j <= m; j += lowbit(j))
                t[i][j] += z;
    }
    int query(int x, int y)
    {
        int res = 0;
        for (int i = x; i >= 1; i -= lowbit(i))
            for (int j = y; j >= 1; j -= lowbit(j))
                res += t[i][j];
        return res;
    }
    signed main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n >> m;
        int op;
        while (cin >> op)
        {
            if (op == 1)
            {
                int a, b, c, d, k;
                cin >> a >> b >> c >> d >> k;
                update(a, b, k);
                update(c + 1, b, -k);
                update(a, d + 1, -k);
                update(c + 1, d + 1, k);
            }
            if (op == 2)
            {
                int a, b;
                cin >> a >> b;
                cout << query(a, b) << "\n";
            }
        }
        return 0;
    }
    
    • 1

    二维树状数组 2:区间修改,单点查询

    信息

    ID
    14247
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    (无)
    递交数
    19
    已通过
    13
    上传者