2023/11/21
树状数组
t[i]，为树状数组；a[i]，为原数组
t[i]代表的区间为a(i-lowbit(i)+1)~a(i)这个区间。
所以求前缀的时候，每次-=lowbit(x),区间是连续接起来的
修改操作，a[x]+val,原数组单点加，那么我们要去树状数组上找哪些节点包含a[x],所以是一个+=lowbit(x)的过程
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 1e6 + 10;
int t[N];
int n, m;
int a[N];
int lowbit(int x)
{
return x & (-x);
}
void add(int x, int val) //对a[x]+val,同时修改t数组，t是真实意义上的树状数组
{
while (x <= n)
{
t[x] += val;
x += lowbit(x);
}
}
int getsum(int x) // 计算sum[1,x] 1到x的前缀和 ，a[1]..a[x]的和
{
int sum = 0;
while (x)
{
sum += t[x];
x -= lowbit(x);
}
return sum;
}
int query(int l, int r) //区间求和 ， 前缀相减
{
return getsum(r) - getsum(l - 1);
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
add(i, a[i]);
}
for (int i = 1; i <= m; i++)
{
int op, x, y;
cin >> op >> x >> y;
if (op == 1)
{
add(x, y);
}
else
{
cout << query(x, y) << endl;
}
}
}
树状数组上二分
因为2的幂次的t[i]数组（即i为2的幂次），他表示的区间就是1~i，所以可以利用位运算的贪心策略从高到底的求最大的区间（第一次的区间表示）
t[i]代表的区间为a(i-lowbit(i)+1)~a(i)这个区间。(关键)
O（n*logn）查询小于x时，前缀的最大下标
const int N = 2e6 + 10;
int t[N];
int n, m;
int a[N];
int lowbit(int x)
{
return x & (-x);
}
void add(int x, int val)
{
while (x <= n)
{
t[x] += val;
x += lowbit(x);
}
}
int getsum(int x)
{
int sum = 0;
while (x)
{
sum += t[x];
x -= lowbit(x);
}
return sum;
}
int query(int s)
{
int c = 0; // 记录当前的前缀和
int pos = 0; // 记录位置
for (int j = 20; j >= 0; j--)
{
if (pos + (1LL << j) <= n && c + t[pos + (1LL << j)] <= s)
{
pos += (1LL << j);
c += t[pos];
}
}
return pos;
}
void solve()
{
int q;
cin >> n >> q;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
add(i, a[i]);
}
while (q--)
{
int op;
cin >> op;
if (op == 1)
{
int x, d;
cin >> x >> d;
add(x, d - a[x]); // 修改a[x]为d
a[x] = d;
}
else
{
int s;
cin >> s;
cout << query(s) << endl;
}
}
}
二维树状数组
对每一个一位的树状数组节点都看成一个树状数组，这样就形成了二维的树状数组，高位同理
二维树状数组 1：单点修改，区间查询
const int N = 4100;
long long t[N][N];
int n, m;
int lowbit(int x)
{
return x & (-x);
}
void add(int x, int y, int val)
{
for (int p = x; p <= n; p += p & (-p))
{
for (int q = y; q <= m; q += q & (-q))
{
t[p][q] += val;
}
}
}
int query(int x, int y)
{
int sum = 0;
for (int p = x; p; p -= p & (-p))
{
for (int q = y; q; q -= q & (-q))
{
sum += t[p][q];
}
}
return sum;
}
void solve()
{
cin >> n >> m;
int op;
while (cin >> op)
{
if (op == 1)
{
int x, y, k;
cin >> x >> y >> k;
add(x, y, k);
}
else
{
int a, b, c, d;
cin >> a >> b >> c >> d;
cout << query(c, d) - query(c, b - 1) - query(a - 1, d) + query(a - 1, b - 1) << endl;
}
}
}