简介
树状数组我的理解就是可以快速求解变化的前缀和的一个比线段树简单的数据结构。
主要思想是通过 lowbit 操作进行。下面的代码为了美观就只给出主要部分，头文件部分以及快读和输出省略不写。
一维树状数组
树状数组 1 ：单点修改，区间查询
一道树状数组的模板题
const int N = 1e6 + 7;
int n, m;
ll a[N];
inline int lowbit(int x) { return x & (-x); }
void add(int i, int c) {
for (; i <= n; i += lowbit(i)) a[i] += c;
}
ll query(int i) {
ll res = 0;
for (; i; i -= lowbit(i)) res += a[i];
return res;
}
void solve() {
n = read(), m = read();
for (int i = 1; i <= n; ++i) {
a[i] += read();
int j = i + lowbit(i);
if (j <= n) a[j] += a[i]; // O(n)建树
}
while (m--) {
int op = read();
if (op & 1) {
int i = read(), x = read();
add(i, x);
}
else {
int l = read(), r = read();
ll ans = query(r) - query(l - 1);
print(ans);
}
}
}
树状数组 2 ：区间修改，单点查询
树状数组维护差分数组。使用差分数组进行建立树状数组，每次维护这个差分数组，之后查询只需要查询该位置差分的前缀和的值就是ans
const int N = 1e6 + 7;
int n, m;
int a[N];
ll b[N];
inline int lowbit(int x) { return x & (-x); }
void add(int i, int z) {
for (; i <= n; i += lowbit(i)) b[i] += z;
}
void add(int l, int r, int z) {
add(l, z);
add(r + 1, -z);
}
ll query(int i) {
ll res = 0;
for (; i; i -= lowbit(i)) res += b[i];
return res;
}
void solve() {
n = read(), m = read();
for (int i = 1; i <= n; ++i) {
a[i] = read();
b[i] += a[i] - a[i - 1];
int j = i + lowbit(i);
if (j <= n) b[j] += b[i];
}
while (m--) {
int op = read();
if (op & 1) {
int l = read(), r = read(), z = read();
add(l, r, z);
}
else {
int i = read();
ll ans = query(i);
print(ans);
}
}
}
树状数组 3 ：区间修改，区间查询
const int N = 1e6 + 7;
int n, m;
int a[N];
ll b1[N], b2[N];
inline int lowbit(int x) { return x & (-x); }
void add(int i, ll z) {
ll tmp = i * z;
for (; i <= n; i += lowbit(i)) b1[i] += z, b2[i] += tmp;
}
void add(int l, int r, int z) {
add(l, z);
add(r + 1, -z);
}
ll query(ll* b, int i) {
ll res = 0;
for (; i; i -= lowbit(i)) res += b[i];
return res;
}
ll query(int l, int r) {
return (r + 1) * query(b1, r) - query(b2, r) - (l * query(b1, l - 1) - query(b2, l - 1));
}
void solve() {
n = read(), m = read();
for (int i = 1; i <= n; ++i) {
a[i] = read();
b1[i] += a[i] - a[i - 1];
b2[i] += 1ll * i * (a[i] - a[i - 1]);
int j = i + lowbit(i);
if (j <= n) b1[j] += b1[i], b2[j] += b2[i];
}
while (m--) {
int op = read();
if (op & 1) {
int l = read(), r = read(), z = read();
add(l, r, z);
}
else {
int l = read(), r = read();
ll ans = query(l, r);
print(ans);
}
}
} P4939 Agent2
一共n个集合，每次操作，每次操作可以把区间中全部集合中元素加一，还有操作叫你输出从第x个集合的元素个数。
区间修改，单点查询。
const int N = 1e7 + 7;
int n, m;
int a[N];
ll b[N];
inline int lowbit(int x) { return x & (-x); }
void add(int i, int z) {
for (; i <= n; i += lowbit(i)) b[i] += z;
}
void add(int l, int r, int z) {
add(l, z);
add(r + 1, -z);
}
ll query(int i) {
ll res = 0;
for (; i; i -= lowbit(i)) res += b[i];
return res;
}
void solve() {
n = read(), m = read();
while (m--) {
int op = read();
if (op == 0) {
int l = read(), r = read();
add(l, r, 1);
}
else {
int i = read();
ll ans = query(i);
print(ans);
}
}
} P5057 [CQOI2006]简单题
与上一题类似，判断修改次数的奇偶即可。
const int N = 1e5 + 7;
int n, m;
int a[N];
ll b[N];
inline int lowbit(int x) { return x & (-x); }
void add(int i, int z) {
for (; i <= n; i += lowbit(i)) b[i] += z;
}
void add(int l, int r, int z) {
add(l, z);
add(r + 1, -z);
}
ll query(int i) {
ll res = 0;
for (; i; i -= lowbit(i)) res += b[i];
return res;
}
void solve() {
n = read(), m = read();
while (m--) {
int op = read();
if (op & 1) {
int l = read(), r = read();
add(l, r, 1);
}
else {
int i = read();
ll ans = query(i) & 1;
print(ans);
}
}
}
P2357 守墓人
区间修改+区间查询，并且把1这个点单独分离出来了。树状数组维护即可。
const int N = 2e5 + 7;
int n, m;
int a[N];
ll b1[N], b2[N];
inline int lowbit(int x) { return x & (-x); }
void add(int i, ll z) {
ll tmp = i * z;
for (; i <= n; i += lowbit(i)) b1[i] += z, b2[i] += tmp;
}
void add(int l, int r, int z) {
add(l, z);
add(r + 1, -z);
}
ll query(ll* b, int i) {
ll res = 0;
for (; i; i -= lowbit(i)) res += b[i];
return res;
}
ll query(int l, int r) {
return (r + 1) * query(b1, r) - query(b2, r) - (l * query(b1, l - 1) - query(b2, l - 1));
}
void solve() {
n = read(), m = read();
for (int i = 1; i <= n; ++i) {
a[i] = read();
b1[i] += a[i] - a[i - 1];
b2[i] += 1ll * i * (a[i] - a[i - 1]);
int j = i + lowbit(i);
if (j <= n) b1[j] += b1[i], b2[j] += b2[i];
}
while (m--) {
int op = read();
if (op == 1) {
int l = read(), r = read(), z = read();
add(l, r, z);
}
else if (op == 2) {
int z = read();
add(1, 1, z);
}
else if (op == 3) {
int z = read();
add(1, 1, -z);
}
else if (op == 4) {
int l = read(), r = read();
ll ans = query(l, r);
print(ans);
}
else {
ll ans = query(1, 1);
print(ans);
}
}
} P1908 逆序对
树状数组的经典用法了，求逆序对。这个题目数据规模很大直接开不下那么大的树状数组，所以想要离散操作。
离散之后在使用树状数组累加当前位置前面有几个比它大的数就是 ans 了。
const int N = 5e5 + 7;
int n, m;
int a[N], b[N];// 原数组 离散数组
int c[N]; // 树状数组
inline int lowbit(int x) { return x & (-x); }
void add(int i, int z) {
for (; i < N; i += lowbit(i)) c[i] += z;
}
ll query(int i) {
ll res = 0;
for (; i; i -= lowbit(i)) res += c[i];
return res;
}
void solve() {
n = read();
for (int i = 1; i <= n; ++i) a[i] = read(), b[i] = a[i];
sort(b + 1, b + 1 + n);
int cnt = unique(b + 1, b + 1 + n) - (b + 1);
for (int i = 1; i <= n; ++i)
a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
ll ans = 0;
for (int i = 1; i <= n; ++i) {
ans += i - 1 - query(a[i]);
add(a[i], 1);
}
print(ans);
} P5094 [USACO04OPEN]MooFest
转换这个式子，把全部的点按照权值排序之后，就可以从小到大枚举权值了，只往前面枚举就可以避免重复。
这样通过两个树状数组去维护位置下标。
一个维护当前数轴位置x前面比x小的数量有几个？
一个维护当前数轴位置x前面比x小的全部点位置之和是多少？
这样就可以去直接计算 ans 了。
const int N = 5e4 + 7;
int n, m;
ll t1[N], t2[N];
inline int lowbit(int x) { return x & (-x); }
void add_num(int i, int z) {
for (; i < N; i += lowbit(i)) t1[i] += z;
}
void add_sum(int i, int z) {
for (; i < N; i += lowbit(i)) t2[i] += z;
}
ll query_num(int i) {
ll res = 0;
for (; i; i -= lowbit(i)) res += t1[i];
return res;
}
ll query_sum(int i) {
ll res = 0;
for (; i; i -= lowbit(i)) res += t2[i];
return res;
}
pai p[N];
void solve() {
n = read();
for (int i = 1; i <= n; ++i)
p[i].first = read(), p[i].second = read();
sort(p + 1, p + 1 + n);
ll x = 0, ans = 0;
for (int i = 1; i <= n; ++i) {
int pos = p[i].second, w = p[i].first;
ll num = query_num(pos);
ll sum = query_sum(pos);
ll s1 = num * pos - sum;
ll s2 = x - sum - (i - 1 - num) * pos;
ans += (s1 + s2) * w;
add_num(pos, 1);
add_sum(pos, pos);
x += pos;
}
print(ans);
}
P3531 [POI2012]LIT-Letters
很经典的题目了，涉及字符串相邻交换肯定和逆序数又有点关系。这里我们需要交换次数最少，也就是逆序数最少。A中每个字母，要放在B中第一个在后面出现的位置。
如果你放在更后面，会产生更多的逆序数，那么也就不是最优解了。
并且如何求解这个逆序数呢，通过B字符串的下标对A字符串标号，求对应下标的逆序数即可。
const int N = 1e6 + 7;
struct Node {
vector<int> pos;
int cnt = 0;
}p[26];
int n, m;
char a[N], b[N];
ll c[N]; // 树状数组
inline int lowbit(int x) { return x & (-x); }
void add(int i, int z) {
for (; i < N; i += lowbit(i)) c[i] += z;
}
ll query(int i) {
ll res = 0;
for (; i; i -= lowbit(i)) res += c[i];
return res;
}
void solve() {
n = read();
scanf("%s", a + 1);
scanf("%s", b + 1);
for (int i = 1; i <= n; ++i)
p[b[i] - 'A'].pos.push_back(i);
ll ans = 0;
for (int i = 1; i <= n; ++i) {
int ch = a[i] - 'A';
int id = p[ch].pos[p[ch].cnt];
p[ch].cnt += 1;
ans += i - 1 - query(id);
add(id, 1);
}
print(ans);
}
珂朵莉的数列
给你n个数需要你求个区间中逆序数总和
出现逆序数就应该往树状数组靠。现在我们想，遇到一对合理的他们产生的贡献是多少？
很显然贡献是。现在我们对于每一个枚举的
来说，他可以产生的贡献就是前方比它大的数
很明显上面那个求合的式子可以使用树状数组优化到
接下来只需要注意一点这个题目规模很大 炸了要开
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
typedef __int128 ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(__int128 x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[100]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 7;
int n, a[N], b[N];
ll tree[N];
inline int lowbit(int x) { return x & (-x); }
void add(int i, ll z) {
for (; i < N; i += lowbit(i)) tree[i] += z;
}
ll query(int i) {
ll res = 0;
for (; i; i -= lowbit(i)) res += tree[i];
return res;
}
void solve() {
n = read();
rep(i, 1, n) b[i] = a[i] = read();
sort(b + 1, b + 1 + n);
int cnt = unique(b + 1, b + 1 + n) - b - 1;
for (int i = 1; i <= n; ++i)
a[i] = lower_bound(b + 1, b + 1 + cnt, a[i]) - b;
ll ans = 0, x = 0;
for (int i = 1; i <= n; ++i) {
ll tmp = x - query(a[i]);
ans += tmp * (n - i + 1);
add(a[i], i);
x+=i;
}
print(ans);
}
int main() {
//int T = read(); while (T--)
solve();
return 0;
} 换个角度思考
给你长度为的序列，并且序列不在改变，
次查询，每次给出
，对于每次的查询你需要回答在这个区间中有几个数字小于等于
。
数据规模
首先观察序列本身是不动的，所以对于每次的查询可以离线处理。
我们对全部的查询按照进行升序排序，同理对
也按照权值进行一次升序排序，并且每个节点记录之前的下标。
这样我们再遍历全部的查询就会变得查询一个从小到大的序列。
这样就可以使用树状数组维护了，依次遍历如果
，把这个数记录的下标处计数1。
最后即是答案。
const int N = 1e6 + 7;
struct Node {
int l, r, k, id;
bool operator < (const Node& A) const {
return k < A.k;
}
}q[N];
pai a[N];
int ans[N], n, m;
int c[N];
inline int lowbit(int x) { return x & (-x); }
void add(int i, int z) {
for (; i <= n; i += lowbit(i)) c[i] += z;
}
int query(int i) {
int res = 0;
for (; i; i -= lowbit(i)) res += c[i];
return res;
}
void solve() {
n = read(), m = read();
rep(i, 1, n) a[i].first = read(), a[i].second = i;
sort(a + 1, a + 1 + n);
rep(i, 1, m) {
int l = read(), r = read(), k = read();
q[i] = { l,r,k,i };
}
sort(q + 1, q + 1 + m);
int j = 1;
rep(i, 1, m) {
int l = q[i].l, r = q[i].r, k = q[i].k, id = q[i].id;
for (; j <= n and a[j].first <= k; ++j) add(a[j].second, 1);
ans[id] = query(r) - query(l - 1);
}
rep(i, 1, m) print(ans[i]);
}
华华开始学信息学
观察发现当这个跳动的比较小的时候直接更新树状数组会出现
。时间复杂度可能达到
这个时候就不能暴力去更新这个单点，那么我们结合分块的思想，当前
小于
的时候使用一个
去统计块中元素的懒惰标记。
那么对于大于的点直接跳表树状数组更新即可。
那么在查询的时候，直接树状数组查询一下的数，还要记得累加上区间中之前小于等于
的懒惰标记的值。
区间里面能被整除的个数就是
，这样累加之后就是
了。
const int N = 1e5 + 7;
int n, m;
ll lazy[500], tree[N];
int lowbit(int x) { return x & (-x); }
void add(int i, int z) {
for (; i <= n; i += lowbit(i)) tree[i] += z;
}
ll query(int i) {
ll res = 0;
for (; i; i -= lowbit(i)) res += tree[i];
return res;
}
void solve() {
n = read(), m = read();
int sqrt_n = sqrt(n);
while (m--) {
int op = read();
if (op & 1) {
int d = read(), k = read();
if (d <= sqrt_n)
lazy[d] += k;
else
for (int i = d; i <= n; i += d)
add(i, k);
}
else {
int l = read(), r = read();
ll ans = query(r) - query(l - 1);
for (int i = 1; i <= sqrt_n; ++i)
ans += (r / i - (l - 1) / i) * lazy[i];
print(ans);
}
}
}
小石的妹子
给出行，每行代表一个人的权值
。
现在需要你给这个人编号，编号越小的越强大。强大的定义是不存在一个
。
那么很好理解首先找到最大的一批人，把他们全部标为
。
再去找最大的一批人，并且之前没有被标为
的人把他们标记成
。
处理完了之后再去处理第二大的以及
第二大的，把他们标记成
，再去往下直到
个人全部被标记完成。
但是这样是不考虑时间复杂度的情况下。在这个题目规模下是会超时的。那么就要想办法优化它。
第一步我们按照降序排序，这样可以得到一个新的序列。
。
并且我们还要记住排序之前的下标记作。
对于序列，说明
已经没有用了，大小我们已经排出来了，如果我们把他对应的下标覆盖掉之前的
值。
对于这个修改后的序列，再次按照
排序，这样每次我们从头到尾遍历一次，我们就可以对每个数对应的
直接记录答案了。
对于每个遍历到的，他的最终编号应该是在他之前所有的
编号的最大值
。
那么这个查询如何作到？树状数组居然可以）我学到了。树状数组不单单可以进行累加操作，居然可以实现一个不修改的单点区间最大。
那在这个查询中，在把区间更新加上就行了。
const int N = 1e6 + 7;
int tree[N], n;
int lowbit(int x) { return x & (-x); }
void update(int i, int val) {
for (; i <= n; i += lowbit(i)) tree[i] = max(tree[i], val);
}
int query(int i) {
int res = 0;
for (; i; i -= lowbit(i)) res = max(res, tree[i]);
return res;
}
struct Node {
int a, b, id;
}p[N];
bool cmp1(const Node& A, const Node& B) { return A.a > B.a; }
bool cmp2(const Node& A, const Node& B) { return A.b > B.b; }
int ans[N];
void solve() {
n = read();
rep(i, 1, n) p[i].a = read(), p[i].b = read(), p[i].id = i;
sort(p + 1, p + 1 + n, cmp1);
rep(i, 1, n) p[i].a = i;
sort(p + 1, p + 1 + n, cmp2);
for (int i = 1; i <= n; ++i) {
ans[p[i].id] = query(p[i].a) + 1;
update(p[i].a, ans[p[i].id]);
}
rep(i, 1, n) print(ans[i]);
}
Forsaken的三维数点
三维空间，每次一个点能量加一，每次查询你需要给出是否存在一个半径下的球包裹的能量大于等于
。如果存在输出最小的半径，否则输出
使用树状数组加上二分可以处理。
那么对于每次输出的能里增加的点，我们可以找到最小的半径可以包括这个点，也就是距离圆心的向上取整值。这个半径下权值加一。
对于每次查询，很显然是符合二分的性质的。如果当前半径符合要求我们就尽可能减少半径，如果当前不够那么就要尽可能增大半径。
输出的情况当且仅当，之前出现过的全部的点都不够
的时候。
这样我们使用一个树状数组统计各个长度下的半径权值。这个题目好像比较水开到的树状数组也可以过，需要求一下最少开多大，应该是
。
这样我们查询就可以在查到答案了。
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 3.5e5 + 7; // ceil(sqrt(2e5*2e5*3)) = 346411
int tree[N], zero;
inline int lowbit(int x) { return x & (-x); }
void add(int i, int z) {
for (; i < N; i += lowbit(i)) tree[i] += z;
}
int query(int i) {
int res = zero;
for (; i; i -= lowbit(i)) res += tree[i];
return res;
}
bool check(int r, int k) {
int res = query(r);
return res >= k;
}
void solve() {
int m = read();
int cnt = 0;
while (m--) {
int op = read();
if (op & 1) {
ll x = read(), y = read(), z = read(); // 1e5 * 1e5 = 1e10炸了int
int r = ceil(sqrt(x * x + y * y + z * z));
if (r == 0) ++zero;
else add(r, 1);
++cnt;
}
else {
int k = read();
if (cnt < k) {
print(-1);
continue;
}
int l = 0, r = N - 1, ans;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid, k))
ans = mid, r = mid - 1;
else l = mid + 1;
}
print(ans);
}
}
}
int main() {
//int T = read(); while (T--)
solve();
return 0;
} 小魂和他的数列
想想逆序数的树状数组实现原理，可以查询到一个位置前面有几个出现过的数。那么再看这个题目。
观察到给出的，那么我们可以对这个
直接暴力枚举，开
个树状数组。
这样就可以通过树状数组记录序列长度为的时候每个位置一共有几个合法的子序列了。
具体的做法就是按照序列的权值做第一关键字递增排序，如果权值相同的点按照下标为第二关键字递减排序。
那么对于这样遍历的每一个人，首先更新长度为的当前所在
，接下来就去依次枚举
的区间长度，找
出现过几次，累加进
这个维度的树状数组即可。
这也是为什么之前我们要对相同的权值点进行第二关键字比较，因为如果不进行处理会计算重复，如果这个题目改一下，把严格递增改成不递减，那就按照第二关键字递增排序，把之前的价值也需要累加，懂这个思想即可。
最后在查询区间长度为的总和即可。
const int N = 5e5 + 7;
int n, k;
ll a[11][N];
inline int lowbit(int x) { return x & (-x); }
void add(int k, int i, int c) {
for (; i <= n; i += lowbit(i)) a[k][i] += c, a[k][i] %= MOD;
}
ll query(int k, int i) {
ll res = 0;
for (; i; i -= lowbit(i)) res += a[k][i], res %= MOD;
return res;
}
struct Node {
int val, id;
bool operator < (const Node& A) const {
if (val != A.val) return val < A.val;
return id > A.id; // 防止相同的数累加多遍
}
}p[N];
void solve() {
n = read(), k = read();
rep(i, 1, n) p[i].val = read(), p[i].id = i;
sort(p + 1, p + 1 + n);
rep(i, 1, n) {
add(1, p[i].id, 1);
ll sum = 0;
rep(j, 2, k) {
sum = query(j - 1, p[i].id - 1);
add(j, p[i].id, sum);
}
}
int ans = query(k, n);
print(ans);
}
二维树状数组
二维树状数组 1：单点修改，区间查询
const int N = 4096 + 7;
ll t[N][N], n, m;
int lowbit(int x) { return x & (-x); }
void update(int x, int y, int c) {
for (int i = x; i <= n; i += lowbit(i))
for (int j = y; j <= m; j += lowbit(j))
t[i][j] += c;
}
ll query(int x, int y) {
ll res = 0;
for (int i = x; i; i -= lowbit(i))
for (int j = y; j; j -= lowbit(j))
res += t[i][j];
return res;
}
ll query(int a, int b, int c, int d) {
ll res = query(c, d) - query(a - 1, d) - query(c, b - 1) + query(a - 1, b - 1);
return res;
}
int main() {
int T = 1;
//T = read();
while (T--) {
n = read(), m = read();
int op;
while (~scanf("%d", &op)) {
if (op & 1) {
int x = read(), y = read(), k = read();
update(x, y, k);
}
else {
int a = read(), b = read(), c = read(), d = read();
ll ans = query(a, b, c, d);
print(ans);
}
}
}
return 0;
} 二维树状数组 2：区间修改，单点查询
const int N = 4096 + 7;
ll t[N][N], n, m;
int lowbit(int x) { return x & (-x); }
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;
}
void update(int a, int b, int c, int d, int z) { // 二维差分更新
update(a, b, z);
update(c + 1, b, -z);
update(a, d + 1, -z);
update(c + 1, d + 1, z);
}
ll query(int x, int y) {
ll res = 0;
for (int i = x; i; i -= lowbit(i))
for (int j = y; j; j -= lowbit(j))
res += t[i][j];
return res;
}
ll query(int a, int b, int c, int d) {
ll res = query(c, d) - query(a - 1, d) - query(c, b - 1) + query(a - 1, b - 1);
return res;
}
int main() {
int T = 1;
//T = read();
while (T--) {
n = read(), m = read();
int op;
while (~scanf("%d", &op)) {
if (op & 1) {
int a = read(), b = read(), c = read(), d = read(), k = read();
update(a, b, c, d, k);
}
else {
int a = read(), b = read();
ll ans = query(a, b);
print(ans);
}
}
}
return 0;
}
二维树状数组 3：区间修改，区间查询
const int N = 2048 + 7;
ll d1[N][N], d2[N][N], d3[N][N], d4[N][N];
int n, m;
void add(int x, int y, ll z) {
for (int i = x; i <= n; i += lowbit(i))
for (int j = y; j <= m; j += lowbit(j)) {
d1[i][j] += z;
d2[i][j] += z * x;
d3[i][j] += z * y;
d4[i][j] += z * x * y;
}
}
void range_add(int xa, int ya, int xb, int yb, ll z) { // 从(xa,ya) 到 (xb,yb) 都加z
add(xa, ya, z);
add(xa, yb + 1, -z);
add(xb + 1, ya, -z);
add(xb + 1, yb + 1, z);
}
ll ask(int x, int y) {
ll res = 0;
for (int i = x; i; i -= lowbit(i))
for (int j = y; j; j -= lowbit(j))
res += d1[i][j] * (x + 1) * (y + 1)
- d2[i][j] * (y + 1)
- d3[i][j] * (x + 1)
+ d4[i][j];
return res;
}
ll range_ask(int xa, int ya, int xb, int yb) {
return ask(xb, yb) - ask(xa - 1, yb) - ask(xb, ya - 1) + ask(xa - 1, ya - 1);
}
void solve() {
n = read(), m = read();
int op;
while (~scanf("%d", &op)) {
if (op & 1) {
int a = read(), b = read(), c = read(), d = read(), z = read();
range_add(a, b, c, d, z);
}
else {
int a = read(), b = read(), c = read(), d = read();
ll ans = range_ask(a, b, c, d);
print(ans);
}
}
} 情人节的电灯泡
单点翻转，区间查询。
const int N = 1e3 + 7;
ll t[N][N], a[N][N], n, m;
int lowbit(int x) { return x & (-x); }
void update(int x, int y, int c) {
for (int i = x; i <= n; i += lowbit(i))
for (int j = y; j <= n; j += lowbit(j))
t[i][j] += c;
}
ll query(int x, int y) {
ll res = 0;
for (int i = x; i; i -= lowbit(i))
for (int j = y; j; j -= lowbit(j))
res += t[i][j];
return res;
}
ll query(int a, int b, int c, int d) {
ll res = query(c, d) - query(a - 1, d) - query(c, b - 1) + query(a - 1, b - 1);
return res;
}
void solve() {
n = read(), m = read();
rep(i, 1, n) rep(j, 1, n)
a[i][j] = read(), update(i, j, a[i][j]);
while (m--) {
int op = read();
if (op & 1) {
int x = read(), y = read();
if (a[x][y]) a[x][y] = 0, update(x, y, -1);
else a[x][y] = 1, update(x, y, 1);
}
else {
int x = read(), y = read(), xx = read(), yy = read();
int ans = query(x, y, xx, yy);
print(ans);
}
}
} Matrix Subtraction
组的输入，每组有一个
代表矩阵的规模。以及
代表你可选择的矩阵规模。
每次你可以选择任意一个的矩阵进行将它全部的元素减一操作，问你能不能把全部的数变成
。
使用二维树状数组进行矩阵检测，从一直检索到
这个点，每次把当前的点
的权值求出来，把整个矩阵都减掉这个值，那么与之对应的就是要判断这个权值是不是负数了，当出现了负数的权值的时候，说明我们之前就有一步操作无法正确进行，因为无法把矩阵元素加
，也就是特判直接输出
。这个题目有点卡常，不能在处理完全部的点之后去从头到尾检测矩阵元素是否有不为
的点，其实需要判断的区间就是每行的末尾以及最后
行中的一些点。稍微优化一下常数就通过了。
const int N = 1e3 + 7;
ll d1[N][N], d2[N][N], d3[N][N], d4[N][N];
int n, m, nn, mm;
inline int lowbit(int x) { return x & (-x); }
void add(int x, int y, ll z) {
for (int i = x; i <= n; i += lowbit(i))
for (int j = y; j <= m; j += lowbit(j)) {
d1[i][j] += z;
d2[i][j] += z * x;
d3[i][j] += z * y;
d4[i][j] += z * x * y;
}
}
void range_add(int xa, int ya, int xb, int yb, ll z) { // 从(xa,ya) 到 (xb,yb) 都加z
add(xa, ya, z);
add(xa, yb + 1, -z);
add(xb + 1, ya, -z);
add(xb + 1, yb + 1, z);
}
ll ask(int x, int y) {
ll res = 0;
for (int i = x; i; i -= lowbit(i))
for (int j = y; j; j -= lowbit(j))
res += d1[i][j] * (x + 1) * (y + 1)
- d2[i][j] * (y + 1)
- d3[i][j] * (x + 1)
+ d4[i][j];
return res;
}
ll range_ask(int xa, int ya, int xb, int yb) {
return ask(xb, yb) - ask(xa - 1, yb) - ask(xb, ya - 1) + ask(xa - 1, ya - 1);
}
void solve() {
ms(d1, 0);
ms(d2, 0);
ms(d3, 0);
ms(d4, 0);
n = read(), m = read(), nn = read(), mm = read();
rep(i, 1, n)
rep(j, 1, m) {
int x = read();
range_add(i, j, i, j, x);
}
rep(i, 1, n - nn + 1) {
rep(j, 1, m - mm + 1) {
ll tmp = range_ask(i, j, i, j);
if (tmp == 0) continue;
if (tmp < 0) {
puts("QAQ");
return;
}
range_add(i, j, i + nn - 1, j + mm - 1, -tmp);
}
if (range_ask(i, m - mm + 1, i, m) != 0) {
puts("QAQ");
return;
}
}
rep(i,n-nn+1,n){
rep(j,1,m-mm+1){
ll tmp = range_ask(i, j, i, j+mm-1);
if(tmp!=0){
puts("QAQ");
return;
}
}
}
puts("^_^");
} 
京公网安备 11010502036488号