本系列是模版系列，会整理
- 题目链接地址
- 参考资料
- AC代码
- 自己挖坑（部分题目有）
关于思路大家可参照题目信息的链接地址或者相关书籍，文章旨在分享代码。
题目信息
- https://loj.ac/p/133
参考资料
- 树状数组
- https://oi-wiki.org/ds/fenwick/
题目描述
这是一道模板题。
给出一个
的零矩阵 A，你需要完成如下操作：
1 x y k：表示元素 A_{x,y} 自增 k；2 a b c d：表示询问左上角为 (a,b)，右下角为 (c,d) 的子矩阵内所有数的和。
输入格式
输入的第一行有两个正整数 n, m； 接下来若干行，每行一个操作，直到文件结束。
输出格式
对于每个 2 操作，输出一个整数，表示对于这个操作的回答。
样例
输入复制
代码语言：javascript复制2 2
1 1 1 3
1 2 2 4
2 1 1 2 2
输出复制
代码语言：javascript复制7
数据范围与提示
- 对于 10% 的数据，n=1；
- 对于另 10% 的数据，m=1；
- 对于全部数据，
，保证操作数目不超过
，且询问的子矩阵存在。
AC代码
代码语言：javascript复制#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
#define endl 'n';
typedef long long LL;
struct node {
LL w, d;
};
struct FenwickTree {
vector<vector<LL>> c;
int n, m;
FenwickTree(int l, int m) :
n(l), c(l 1, vector<LL>(m 1)), m(m) {}
int lowbit(int a) {
return (-a) & a;
}
LL cnt(int x, int y) {
LL ans = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
for (int j = y; j > 0; j -= lowbit(j)) {
ans = c[i][j];
}
}
return ans;
}
void add(int x, int y, LL w) {
for (int i = x; i <= n; i = lowbit(i)) {
for (int j = y; j <= m; j = lowbit(j)) {
c[i][j] = w;
}
}
}
LL ask(int x1, int y1, int x2, int y2) {
return cnt(x2, y2) - cnt(x2, y1 - 1) - cnt(x1 - 1, y2) cnt(x1 - 1, y1 - 1);
}
};
void best_coder() {
int n, m;
scanf("%d%d", &n, &m);
FenwickTree ft(n, m);
int a;
while(~scanf("%d", &a)) {
if (a == 1) {
int l, r;
LL w;
scanf("%d%d%lld", &l, &r, &w);
ft.add(l, r, w);
} else {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%lldn", ft.ask(x1, y1, x2, y2));
}
}
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// freopen("xxx.in", "r", stdin);
// freopen("xxx.out", "w", stdout);
// 小码匠
best_coder();
// 最优解
// happy_coder();
// fclose(stdin);
// fclose(stdout);
return 0;
}
