• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# 二维树状数组基本操作

1周前 (06-11) 12次浏览

# 单点修改区间查询

LOJ #133. 二维树状数组 1：单点修改，区间查询

``````const int N = 4106;

{
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}

int n, m;
ll t[N][N];

void modify(int x, int y, ll val)
{
for (int i = x; i <= n; i += i & -i)
for (int j = y; j <= m; j += j & -j)
t[i][j] += val;
}

ll query(int x, int y)
{
ll ans = 0;
for (int i = x; i; i -= i & -i)
for (int j = y; j; j -= j & -j)
ans += t[i][j];
return ans;
}

int main()
{
for (int op, a, b, c, d; scanf ("%d", &op) != EOF; )
{
printf ("%lldn", query(c, d) - query(a - 1, d) - query(c, b - 1) + query(a - 1, b - 1));
}
return 0;
}
``````

# 单点修改区间查询

LOJ #135. 二维树状数组 3：区间修改，区间查询

[begin{aligned}&sum_{x=1}^{a}sum_{y=1}^{b}sum_{i=1}^{x}sum_{j=1}^{y}t_{i,j}\
=&sum_{i=1}^{a}sum_{j=1}^{b}(a-i+1)(b-j+1)t_{i,j}\
=&(a+1)(b+1)sum_{i=1}^{a}sum_{j=1}^{b}t_{i,j}-\
&(b+1)sum_{i=1}^{a}sum_{j=1}^{b}t_{i,j}cdot i-\
&(a+1)sum_{i=1}^{a}sum_{j=1}^{b}t_{i,j}cdot j+\
&sum_{i=1}^{a}sum_{j=1}^{b}t_{i,j}cdot ijend{aligned}]

``````const int N = 4106;

{
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}

int n, m;
ll t[4][N][N];

void modify(int x, int y, ll val)
{
for (int i = x; i <= n; i += i & -i)
for (int j = y; j <= m; j += j & -j)
t[0][i][j] += val,
t[1][i][j] += val * x,
t[2][i][j] += val * y,
t[3][i][j] += val * x * y;
}

ll query(int x, int y)
{
ll ans = 0;
for (int i = x; i; i -= i & -i)
for (int j = y; j; j -= j & -j)
ans += (x + 1) * (y + 1) * t[0][i][j] -
(y + 1) * t[1][i][j] -
(x + 1) * t[2][i][j] +
t[3][i][j];
return ans;
}

int main()
{