1 条题解

  • 0
    @ 2025-6-14 10:58:01
    #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 x, y, k;
                cin >> x >> y >> k;
                update(x, y, k);
            }
            if (op == 2)
            {
                int a, b, c, d, delta;
                cin >> a >> b >> c >> d;
                cout << query(c, d) -
                            query(c, b - 1) -
                            query(a - 1, d) +
                            query(a - 1, b - 1)
                     << "\n";
            }
        }
        return 0;
    }
    
    • 1

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

    信息

    ID
    14246
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    (无)
    递交数
    45
    已通过
    15
    上传者