【高级数据结构】树状数组

一、树状数组的介绍

1.思维导引

树状数组 ( B i n a r y I n d e x e d T r e e , B I T ) (Binary Indexed Tree,BIT) (BinaryIndexedTree,BIT)是利用数的二进制特征进行检索的一种树状的结构。

如何利用二分的思想高效地求前缀和?
如图 4.7 4.7 4.7所示, 以 A A A = [ a 1 , =[a_1, =[a1, a 2 a_2 a2 , a 3 a_3 a3 a 8 ] a_8] a8]为例,将二叉树的结构画成树状。

这幅图是树状数组的核心,理解了它,就能明白树状数组的一切操作。

4.7 4.7 4.7圆圈中标记有数字的节点,存储的是称为树状数组的 t r e e [ ] tree[] tree[]

一个节点上的 t r e e [ ] tree[] tree[]的值就是其树下的直连的子节点的和。

例如:
t r e e [ 1 ] = a 1 tree[1]=a_1 tree[1]=a1
t r e e [ 2 ] = t r e e [ 1 ] + a 2 tree[2]=tree[1]+a_2 tree[2]=tree[1]+a2
t r e e [ 3 ] = a 3 tree[3]=a_3 tree[3]=a3
t r e e [ 4 ] = t r e e [ 2 ] + t r e e [ 3 ] + a 4 tree[4]=tree[2]+tree[3]+a_4 tree[4]=tree[2]+tree[3]+a4

t r e e l [ 8 ] = t r e e [ 4 ] + t r e e [ 6 ] + t r e e [ 7 ] + a 8 treel[8]=tree[4]+tree[6]+tree[7]+a_8 treel[8]=tree[4]+tree[6]+tree[7]+a8

利用 t r e e [ ] tree[] tree[]可以高效地完成以下两个操作。

( 1 ) (1) (1)查询,即求前缀和 s u m sum sum

例如:
s u m ( 8 ) = t r e e [ 8 ] sum(8)=tree[8] sum(8)=tree[8], s u m ( 7 ) = t r e e [ 7 ] + t r e e 6 ] + t r e e [ 4 ] sum(7)=tree[7]+tree6]+tree[4] sum(7)=tree[7]+tree6]+tree[4]
s u m ( 6 ) = t r e e [ 6 ] + t r e e [ 4 ] sum(6)=tree[6]+tree[4] sum(6)=tree[6]+tree[4]

如图 4.7 4.7 4.7所示,下图中的虚线箭头是计算 s u m ( 7 ) sum(7) sum(7)的过程。

显然,计算复杂度为 O ( l o g 2 n ) O(log2n) O(log2n),这样就达到了快速计算前缀和的目的。

( 2 ) (2) (2)维护。

t r e e [ ] tree[] tree[]本身的维护也是高效的。当元素 a a a发生改变时,能以 O ( l o g 2 n ) O(log_2n) O(log2n)的高效率修改 t r e e [ ] tree[] tree[]的值。

例如,更新了 a 3 a_3 a3, ,那么只需要修改 t r e e [ 3 ] , t r e e [ 4 ] . t r e e [ 8 ] tree[3],tree[4].tree[8] tree[3],tree[4].tree[8],即修改它和它上面的那些节点:父节点(后文指出, x x x 的父节点是 x + l o w b i t ( x ) ) x+lowbit(x)) x+lowbit(x))以及父节点的父节点。

有了方案,剩下的问题是如何快速计算出 t r e e [ ] tree[] tree[]

观察查询和维护两个操作,发现(读者完全可以自己观察树状数组的原理图,根据二进制的特征得到以下结论):

( 1 ) (1) (1)查询的过程是每次去掉二进制的最后的 1 1 1。例如,求 s u m ( 7 ) = t r e e [ 7 ] + t r e e [ 6 ] + t r e e [ 4 ] sum(7)= tree[7]+tree[6]+tree[4] sum(7)=tree[7]+tree[6]+tree[4],

步骤如下:

1 、 7 1、7 17的二进制是 111 111 111,去掉最后的 1 1 1,得 110 110 110,即 t r e e [ 6 ] tree[6] tree[6];
2 、 2、 2去掉 6 6 6的二进制 110 110 110的最后一个1 , , , 100 100 100,即 t r e e [ 4 ] tree[4] tree[4];
3 、 3、 3 4 4 4 的二进制是 100 100 100,去掉 1 1 1之后就没有了。

( 2 ) (2) (2)维护的过程是每次在二进制的最后的 1 1 1上加 1 1 1

例如,更新了 a 3 a_3 a3 ,需要修改 t r e e [ 3 ] 、 t r e e [ 4 ] , t r e e [ 8 ] tree[3]、tree[4],tree[8] tree[3]tree[4],tree[8]

步骤如下:

1 、 1、 1 3 3 3的二进制是 11 11 11,在最后的 1 1 1上加 1 1 1 100 100 100,即 4 4 4,修改 t r e e [ 4 ] tree[4] tree[4];
2 、 2、 2 4 4 4的二进制是 100 100 100,在最后的 1 1 1上加 1 1 1,得 1000 1000 1000,即 8 8 8,修改 t r e e [ 8 ] tree[8] tree[8];
3 、 3、 3继续修改 t r e e [ 16 ] tree[16] tree[16], t r e e [ 32 ] tree[32] tree[32]等。

最后,树状数组归结到一个关键问题:如何找到一个数的二进制的最后一个 1 1 1

2.神奇的 l o w b i t ( x ) lowbit(x) lowbit(x)

l o w b i t ( x ) = x & − x lowbit(x)=x\&-x lowbit(x)=x&x功能是找到 x x x 的二进制数的最后一个 1 1 1
其原理是利用了负数的补码表示,补码是原码取反加 1 1 1

例如, x = 6 = 0000011 0 2 x =6 =00000110_2 x=6=000001102, − x = x 补 = 1111101 0 2 -x =x_补=11111010_2 x=x=111110102

那么 l o w b i t ( x ) = x & ( − x ) = 1 0 2 = 2 lowbit(x)=x\&(-x)=10_2=2 lowbit(x)=x&(x)=102=2

l o w b i t ( x ) lowbit(x) lowbit(x)的结果如表 4.1 4.1 4.1所示 ( x = 1 − 9 ) (x =1-9) (x=19)
在这里插入图片描述在这里插入图片描述

m = l o w b i t ( x ) , t r e e [ x ] m =lowbit(x) , tree[x] m=lowbit(x),tree[x]的值是把 a x a_x ax。和它前面共 m m m 个数相加的结果。如表 4.1 4.1 4.1所示。

例如, l o w b i t ( 6 ) = 2 lowbit(6)=2 lowbit(6)=2,有 t r e e [ 6 ] = a 5 + a 6 tree[6]=a_5+a_6 tree[6]=a5+a6.

t r e e [ ] tree[] tree[]是通过 l o w b i t ( ) lowbit() lowbit()计算出的树状数组,它能够以二分的复杂度存储一个数列的数据。
具体地, t r e e [ x ] tree[x] tree[x]中存储的是区间 [ x — l o w b i t ( x ) + 1 , r ] [x—lowbit(x)+1,r] [xlowbit(x)+1,r]中每个数的和。

4.1 4.1 4.1可以画成图 4.8 4.8 4.8

横条中的黑色部分表示 t r e e [ x ] tree[x] tree[x],它等于横条上元素相加的和。
在这里插入图片描述

二、树状数组的基本应用

1.单点修改+区间查询

这是最常规的树状数组模板,代码如下:

#include<bits/stdc++.h>
using namespace std;
const int maxn =5e5 + 10;
const int maxm = 5e5 + 10;
#define int long long
int n,m;
int tree[maxn]; //树状数组
/* 树状数组 */
inline int lowbit(int x) { //神奇的lowbit函数!return x & (-x);
}
//单点修改
void add(int i,int x) {while (i <= n) {tree[i] += x;i += lowbit(i);}
}
//区间查询 返回1-i的和
int query(int i) {int res = 0;while (i > 0) {res += tree[i];i -= lowbit(i);}return res;
}
signed main() {ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) {int x;cin >> x;add(i, x);}while (m--) {int op, x, y;cin >> op;if (op == 1) {cin >> x >> y;add(x, y);}else {cin >> x >> y;cout << query(y) - query(x - 1) << "\n";}}}

2.区间修改+单点查询

我们使用差分的思想来建树,我们知道,差分的前缀和是单个点的值。
因此,我们对 1 − i 1-i 1i的差分数组求一次前缀和就能得到 a [ i ] a[i] a[i]的值了,而修改操作就类似于差分的修改,在左右两端修改即可,即在 i i i + x +x +x i + 1 i+1 i+1 − x -x x
代码如下:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
const int maxm = 1e5 + 10;
int c[maxn];//树状数组
int a[maxn]; //原数组
int n,m;
inline int lowbit(int x) {return x & (-x);
}
void add(int i,int x) {while (i <= n) {c[i] += x;i += lowbit(i);}
}
//查找1-i的区间和
int query(int i) {int res = 0;while (i > 0) {res += c[i];i -= lowbit(i);}return res;
}
void solve() {cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i];add(i,a[i]-a[i-1]); //差分建树}while (m--) {int op, l, r,x;cin >> op;if (op == 1) {cin >> l >> r>>x;add(l, x);add(r + 1, -x);}else {cin >>l;cout << query(l)<< '\n';}}
}
signed main() {   ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//FILE* stream;//freopen_s(&stream, "stdcin.txt", "r", stdin);int t = 1;//cin >> t;while (t--) {solve();}//fclose(stdin);}

3.区间修改+区间查询

操作 ( 1 ) (1) (1)是区间修改,操作 ( 2 ) (2) (2)是区间查询。

首先,求区间和 s u m ( L , R ) = a [ L ] + a [ L + 1 ] + … + a [ R ] = s u m ( 1 , R ) − s u m ( 1 , L − 1 ) sum(L ,R)=a[L]+a[L+1]+…+a[R]=sum(1,R )-sum(1,L-1) sum(L,R)=a[L]+a[L1]++a[R]=sum(1,R)sum(1,L1),问题转换为求 s u m ( 1 , k ) sum(1,k) sum(1,k)

定义一个差分数组 D D D,它和原数组 a a a的关系仍然是
D [ k ] = a [ k ] − a [ k − 1 ] D[k]=a[k]-a[k-1] D[k]=a[k]a[k1] ,
a [ k ] = D [ 1 ] + D [ 2 ] + … + D [ k ] a[k]=D[1]+D[2]+…+D[k] a[k]=D[1]+D[2]+D[k]

下面推导区间和,看它与求前缀和有没有关系,如果有关系,就能用树状数组。

a 1 + a 2 + … + a k a_1+a_2+…+a_k a1+a2+ak
= D 1 + ( D 1 + D 2 ) + ( D 1 + D 2 + D 3 ) + … + ( D 1 + D 2 + … + D k ) =D_1+(D_1+D_2)+(D_1+D_2+D_3)+…+(D_1+D_2+…+D_k) =D1+(D1+D2)(D1+D2+D3)(D1+D2+Dk)
= k D 1 + ( k − 1 ) D 2 + ( k − 2 ) D 3 , + … + ( k − ( k − 1 ) ) D k , =kD_1+(k-1)D_2+(k-2)D_3,+…+(k-(k-1))D_k, =kD1+(k1)D2+(k2)D3,+(k(k1))Dk,
= k ( D 1 + D 2 + … + D k ) − ( D 2 + 2 D 3 + … + ( k − 1 ) D k ) =k(D_1+D_2+…+D_k)-(D_2+2D_3+…+(k-1)D_k) =k(D1+D2Dk)(D2+2D3+(k1)Dk)
= k ∑ i = 1 k D i − ∑ i = 1 k ( i − 1 ) D i =k\sum_{i=1}^{k} D_i-\sum_{i=1}^{k}(i -1)D_i =ki=1kDii=1k(i1)Di

公式最后一行求两个前缀和,用两个树状数组分别处理,一个实现 D i D_i Di,另一个实现 ( i − 1 ) D i (i-1)D_i (i1)Di

代码如下:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
const int maxm = 5e5 + 10;
#define int long long
int n, m;
int tree1[maxn]; //差分树状数组
int tree2[maxn]; //(i-1)*tree1[i]树状数组
int a[maxn]; //原数组
/* 树状数组 */
inline int lowbit(int x) { //神奇的lowbit函数!return x & (-x);
}
/* 维护两个树状数组 */
//区间修改1
void add1(int i, int x) {while (i <= n) {tree1[i] += x;i += lowbit(i);}
}
//区间修改2
void add2(int i, int x) {while (i <= n) {tree2[i] += x;i += lowbit(i);}
}//区间查询1
int query1(int i) {int res = 0;while (i > 0) {res += tree1[i];i -= lowbit(i);}return res;
}
//区间查询2
int query2(int i) {int res = 0;while (i > 0) {res += tree2[i];i -= lowbit(i);}return res;
}
signed main() {cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i];add1(i, a[i] - a[i - 1]); //差分建树add2(i, (i - 1) * (a[i] - a[i - 1]));//(i-1)*tree1[i]建树}while (m--) {int op, x, y, k;cin >> op;if (op == 1) {cin >> x >> y >> k; //修改区间add1(x, k);add1(y + 1, -k);add2(x, (x - 1) * k);add2(y + 1, y * (-k));}else {cin >> x >> y;cout << y * query1(y) - (x - 1) * query1(x - 1) - (query2(y) - query2(x - 1)) << "\n"; //区间查询}}}

三、树状数组的扩展应用

1.树状数组求二维偏序(逆序对)

一种方法是通过归并排序来实现,也可以使用树状数组来实现,下面的代码实现了这两种方法:

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 5e5 + 10;
const int maxm = 5e5 + 10;
#define pii pair<int,int>
#define int long long
int n;
int tree[maxn];
inline int lowbit(int x) {return x & (-x);
}
void add(int i,int x) {while (i <= n) {tree[i] += x;i += lowbit(i);}
}
int query(int i) { int res = 0;while (i > 0) {res += tree[i];i -= lowbit(i);}return res;
}
void solve1() { //逆序对第一种解法-树状数组cin >> n;vector<pii>a(n + 1);for (int i = 1; i <= n; ++i) {cin >> a[i].first;a[i].second = i;}//离散化sort(a.begin() + 1, a.end()); vector<int>b(n + 1);for (int i = 1; i <= n; ++i) {b[a[i].second] = i; }int res = 0;for (int i = 1; i <= n; ++i) {add(b[i], 1);res +=query(n) - query(b[i]);}cout << res << endl;
}
int b[maxn]; //辅助数组
int a[maxn]; //原序列
int res = 0; //逆序对的个数
void merge(int l,int mid,int r) { //排序int i = l, j = mid + 1 ;int k = 0;while (i <= mid && j <= r) {if (a[i] > a[j]) {b[++k] = a[j++];res += mid - i + 1; //记录逆序对个数}else {b[++k] = a[i++];}}while (i <= mid) b[++k] = a[i++];while (j <= r) b[++k] = a[j++];for (int i = 1; i <= k; ++i) { //把辅助数组拷贝到原数组a[l + i - 1] = b[i];}
}
void mergesort(int l,int r) { //划分if (l >= r) return; //边界int mid = l + r >> 1;mergesort(l, mid); mergesort(mid + 1, r);merge(l, mid, r);
}
void solve2() { //第二种解法-归并排序cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];}mergesort(1, n);cout << res << endl;
}signed main() {//solve1();solve2();return 0;
}

2.树状数组求区间最值

用暴力法求解,复杂度为 O ( M N ) O(MN) O(MN)

下面用树状数组求解。

在标准前缀和树状数组中, t r e e [ x ] tree[x] tree[x]中存储的是 [ x − l o w b i t ( x ) + 1 , x ] [ x-lowbit(x )+1,x] [xlowbit(x)+1,x]中每个数的和。

在求最值的树状数组中, t r e e [ x ] tree[x] tree[x]记录 [ x 一 l o w b i t ( x ) + 1 , x ] [x一lowbit(x)+1,x] [xlowbit(x)+1,x]内所有数的最大值。

阅读下面内容时,请对照树状数组原理图,如图 4.11 4.11 4.11所示。
在这里插入图片描述

(1)单点修改:

u p d a t e ( x , v a l u e ) update( x, value) update(x,value)。用 v a l u e value value更新 t r e e [ z ] tree[z] tree[z]的最大值,并更新树状数组上被它影响的节点。

例如,修改 x = 4 x=4 x=4,步骤如下:

修改 x x x子树上直连的 t r e e [ 2 ] , t r e e [ 3 ] tree[2],tree[3] tree[2],tree[3]

修改 x x x 的父节点 t r e e [ 8 ] tree[8] tree[8],以及 t r e e [ 8 ] tree[8] tree[8]的直连子节点 t r e e [ 6 ] tree[6] tree[6], t r e e [ 7 ] tree[7] tree[7]等。

每步复杂度为 O ( l o g 2 n ) O(log_2n) O(log2n),共 O ( l o g 2 n ) O(log_2n) O(log2n)步,总复杂度为 O ( ( l o g 2 n ) 2 ) O((log_2n)^ 2) O((log2n)2)

注意一个特殊情况,初始化时需要修改所有 n n n个数,复杂度为 O ( n ( l o g 2 n ) 2 ) O(n(log_2n)^2) O(n(log2n)2) ,符合要求。

( 2 ) (2) (2)区间最值查询: q u e r y ( ) query() query()

关于区间 [ L , R ] [L,R] [L,R]的最值,分两种情况讨论。

1. R − L ≥ l o w b i t ( R ) 1.R-L \geq lowbit(R) 1.RLlowbit(R)

对照图 4.11 4.11 4.11,即 [ L , R ] [L,R] [L,R]区间包含了 t r e e [ R ] tree[R] tree[R]直连子节点的个数,此时直接使用 t r e e [ R ] tree[R] tree[R]值: q u e r y ( L , R ) = m a x ( t r e e [ R ] , q u e r y ( L , R − l o w b i t ( R ) ) ) query(L,R)=max(tree[R],query(L,R-lowbit(R))) query(L,R)=max(tree[R],query(L,Rlowbit(R)))

2. R − L ≤ l o w b i t ( R ) 2.R-L\leq lowbit(R) 2.RLlowbit(R)

上述包含关系不成立,先使用 a [ R ] a[R] a[R]的值,然后向前递推: q u e r y ( L , R ) = m a x ( a [ R ] , q u e r y ( L , R − 1 ) ) query(L,R)=max(a[R],query(L,R-1)) query(L,R)=max(a[R],query(L,R1))

q u e r y ( ) query() query()的复杂度仍然为 O ( ( l o g 2 n ) 2 ) O((log_2n)^2) O((log2n)2)

思路

有很多种求区间最值的方法,这里选择使用树状数组来求区间最值,时间复杂度较差,单次修改和查询都为 O ( ( l o g 2 n ) 2 ) O((log_2n)^2) O((log2n)2),能通过此题。

代码

const int N = 1e5 + 10;
int a[N];
int tree[N];
int n, m;
void update(int x, int val) {for (int i = x; i <= n; i += lowbit(i)) {tree[i] = val;for (int j = 1; j < lowbit(x); j <<= 1) {tree[i] = std::max(tree[i], tree[i - j]);}}
}int query(int L, int R) {int res = -INF;while (L <= R) {res = std::max(res, a[R]);R--;while (R - L >= lowbit(R)) {res = std::max(res, tree[R]);R -= lowbit(R);}}return res;
}
void solve() {cin >> n >> m;for (int i = 1; i <= n; ++i) {cin >> a[i];update(i, a[i]);}while (m--) {int l, r;cin >> l >> r;std::cout << query(l, r) << "\n";}}
//main 函数 
signed main() {std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);int t = 1;//cin >> t;while (t--) {solve();}return 0;
}

3.二维区间修改+查询

二维区间修改+查询和一维区间修改+查询类似,都是建立在差分的思想上,二维需要有四个树状数组来维护,具体的推导过程如下:

( 1 ) (1) (1)二维区间修改

如何实现区间修改?需要结合二维差分数组。定义一个二维差分数组 D [ i ] [ j ] D[i][j] D[i][j],它与矩阵元素 a [ c ] [ d ] a[c][d] a[c][d]的关系为

D [ i ] [ j ] = a [ i ] [ j ] − a [ i − 1 ] [ j ] − a [ i ] [ j − 1 ] + a [ i − 1 ] [ j − 1 ] D[i][j]=a[i][j]-a[i -1][j]-a[i][j -1]+a[i-1][j-1] D[i][j]=a[i][j]a[i1][j]a[i][j1]a[i1][j1]

对照图 4.9 4.9 4.9, D [ i ] [ j ] D[i][j] D[i][j]就是阴影面积。

a [ c ] [ d ] = ∑ i = 1 c ∑ j = 1 d a[c][d]=\sum_{i=1}^{c} \sum_{j=1}^{d} a[c][d]=i=1cj=1d,可看作对以 ( 1 , 1 ) (1,1) (1,1) ( c , d ) (c ,d) (c,d)为顶点的矩阵内的 D [ i ] [ j ] D[i][j] D[i][j]求和。

它们同样满足“差分是前缀和的逆运算”。

进行区间修改时,在 u p d a t e ( ) update() update()函数中,每次第 i i i行减少 l o w b i t ( i ) lowbit(i) lowbit(i),第 j j j列减少 l o w b i t ( j ) lowbit(j) lowbit(j) ,复杂度为 O ( l o g 2 n l o g 2 m ) O(log_2nlog_2m) O(log2nlog2m)

( 2 ) (2) (2)二维区间查询

查询以 ( a , b ) (a ,b) (a,b) ( c , d ) (c ,d) (c,d)为顶点的矩阵区间和,
对照图 4.10 4.10 4.10的阴影部分,有
∑ i = a c ∑ j = b d a [ i ] [ j ] = ∑ i = 1 c ∑ j = 1 d a [ i ] [ j ] − ∑ i = 1 c ∑ j = 1 b − 1 a [ i ] [ j ] − ∑ i = 1 a − 1 ∑ j = 1 d a [ i ] [ j ] + ∑ i = 1 a − 1 ∑ j = 1 b − 1 a [ i ] [ j ] \sum_{i=a}^{c} \sum_{j=b}^{d} a[i][j]=\sum_{i=1}^{c} \sum_{j=1}^{d} a[i][j]-\sum_{i=1}^{c} \sum_{j=1}^{b-1} a[i][j]-\sum_{i=1}^{a-1} \sum_{j=1}^{d} a[i][j]+\sum_{i=1}^{a-1} \sum_{j=1}^{b-1} a[i][j] i=acj=bda[i][j]=i=1cj=1da[i][j]i=1cj=1b1a[i][j]i=1a1j=1da[i][j]+i=1a1j=1b1a[i][j]

问题转换为计算 ∑ i = 1 n ∑ j = 1 m \sum_{i=1}^{n}\sum_{j=1}^{m} i=1nj=1m,根据它与差分数组 D D D的关系进行变换,有:

∑ i = 1 n ∑ j = 1 m a [ i ] [ j ] = ∑ i = 1 n ∑ j = 1 m ∑ k = 1 i ∑ l = 1 j D [ k ] [ l ] = ∑ i = 1 n ∑ j = 1 m D [ i ] [ j ] × ( n − i + 1 ) × ( m − j + 1 ) = ( n + 1 ) ( m + 1 ) ∑ i = 1 n ∑ j = 1 m D [ i ] [ j ] − ( m + 1 ) ∑ i = 1 n ∑ j = 1 m D [ i ] [ j ] × i − ( n + 1 ) ∑ i = 1 n ∑ j = 1 m D [ i ] [ j ] × j + ∑ i = 1 n ∑ j = 1 m D [ i ] [ j ] × i × j \begin{aligned} & \sum_{i=1}^{n} \sum_{j=1}^{m} a[i][j] \\ = & \sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{k=1}^{i} \sum_{l=1}^{j} D[k][l] \\ = & \sum_{i=1}^{n} \sum_{j=1}^{m} D[i][j] \times(n-i+1) \times(m-j+1) \\ = & (n+1)(m+1) \sum_{i=1}^{n} \sum_{j=1}^{m} D[i][j]-(m+1) \sum_{i=1}^{n} \sum_{j=1}^{m} D[i][j] \times i- \\ & (n+1) \sum_{i=1}^{n} \sum_{j=1}^{m} D[i][j] \times j+\sum_{i=1}^{n} \sum_{j=1}^{m} D[i][j] \times i \times j \end{aligned} ===i=1nj=1ma[i][j]i=1nj=1mk=1il=1jD[k][l]i=1nj=1mD[i][j]×(ni+1)×(mj+1)(n+1)(m+1)i=1nj=1mD[i][j](m+1)i=1nj=1mD[i][j]×i(n+1)i=1nj=1mD[i][j]×j+i=1nj=1mD[i][j]×i×j

这是 4 4 4个二维树状数组。

代码如下:

思路

使用二维线段树也可以实现,使用二维树状数组比较代码量比较小一点,并且空间复杂度也小一点。

代码

const int N = 2100 + 10;
int tree1[N][N], tree2[N][N], tree3[N][N], tree4[N][N];
char ch;
int n, m;
void update(int x, int y, int val) {for (int i = x; i <= n; i += lowbit(i)) {for (int j = y; j <= m; j += lowbit(j)) {tree1[i][j] += val;tree2[i][j] += x * val;tree3[i][j] += y * val;tree4[i][j] += x * y * val;}}
}int query(int x, int y) {int res = 0;for (int i = x; i > 0; i -= lowbit(i)) {for (int j = y; j > 0; j -= lowbit(j)) {res += (x + 1) * (y + 1) * tree1[i][j] - (y + 1) * tree2[i][j] - (x + 1) * tree3[i][j] + tree4[i][j];}}return res;
}void solve() {cin >> ch >> n >> m;int a, b, c, d;while (cin >> ch >> a >> b >> c >> d) {if (ch == 'L') {int val;cin >> val;update(a, b, val);update(a, d+1, -val);update(c+1, b, -val);update(c+1, d+1, val);}else {std::cout << query(c, d) + query(a - 1, b - 1) - query(a - 1, d) - query(c, b - 1) << "\n";}}}
//main 函数 
signed main() {std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);int t = 1;//cin >> t;while (t--) {solve();}return 0;
}

4.离线算法

这题一种方法是在线通过主席树来做,另一种方法是离线排序后使用树状数组,下面两种方法都实现了:

解法一(主席树)

思路

首先我们需要查询 [ L , R ] [L,R] [L,R]中不同种类数字的个数。

我们可以在主席树的每个位置存入每个数下一次出现的位置(如果不出现,则存入 n + 1 n+1 n+1)。
这样做有什么用呢?

考虑一个区间 [ 1 , 2 , 3 , 3 , 4 , 2 , 5 ] [1,2,3,3,4,2,5] [1,2,3,3,4,2,5],假设我们要查询区间 [ 2 , 3 , 3 ] [2,3,3] [2,3,3],而我们在主席树中存放的位置为 [ 8 , 4 , 8 ] [8,4,8] [8,4,8],可以发现,我们只需要在主席树上查找区间内大于 R R R的数有多少个,而对于这样的查询,主席树显然是很容易做到的。

代码
const int N = 1e6 + 10;
int root[N];
int tot = 0;
struct node {int l, r, cnt;
}tree[N * 40];
#define ls(x) tree[x].l
#define rs(x) tree[x].r
int n;
void build(int l, int r, int& u) {u = ++tot;if (l == r) return;int mid = l + r >> 1;build(l, mid, ls(u));build(mid + 1, r, rs(u));
}
void insert(int u, int& v, int l, int r, int val) {v = ++tot;tree[v] = tree[u];tree[v].cnt++;if (l == r) return;int mid = l + r >> 1;if (val <= mid) {insert(ls(u), ls(v), l, mid, val);}else {insert(rs(u), rs(v), mid + 1, r, val);}
}
int query(int u, int v, int l, int r, int k) {if (l == r) return tree[v].cnt - tree[u].cnt;int res = 0;int s = tree[rs(v)].cnt - tree[rs(u)].cnt;int mid = l + r >> 1;if (k <= mid) {res += s;res += query(ls(u), ls(v), l, mid, k);}else res += query(rs(u), rs(v), mid+1, r, k);return res;
}
int a[N], head[N], nxt[N];
void solve() {cin >> n;build(1, n+1, root[0]);memset(head, -1, sizeof(head));for (int i = 1; i <= n; ++i) {cin >> a[i];if (head[a[i]] == -1) head[a[i]] = i;else {int t = head[a[i]];head[a[i]] = i;nxt[t] = i;}}for (int i = 1; i <= n; ++i) {if (!nxt[i]) nxt[i] = n + 1;insert(root[i - 1], root[i], 1, n + 1, nxt[i]);}int q;cin >> q;while (q--) {int l, r;cin >> l >> r;int res = query(root[l - 1], root[r], 1, n + 1, r + 1);cout << res << "\n";}
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(0);int t = 1;//cin >> t;while (t--) {solve();}
}

解法二(离线+树状数组)

思路

首先我们把序列存起来,按照右端点从小到大排序。
为什么呢?
考虑一段区间 [ 1 , 2 , 3 , 3 , 4 , 2 , 5 ] [1,2,3,3,4,2,5] [1,2,3,3,4,2,5],我们依次从左到右存入相应位置上(下标 i i i)的 1 1 1,在序列 [ 1 , 2 , 3 ] [1,2,3] [1,2,3]中,树状数组中的序列为: [ 1 , 1 , 1 ] [1,1,1] [1,1,1]
如果我们发现出现了重复的数字,我们对 l a s t [ a [ i ] ] last[a[i]] last[a[i]]的位置贡献 − 1 -1 1,然后在当前位置加上贡献,此时序列为: [ 1 , 1 , 0 , 1 ] [1,1,0,1] [1,1,0,1]
可以发现这样的操作类似于差分序列,但是这样的修改会影响到右端点为 3 3 3的查询。
但是我们开头说了:

首先我们把序列存起来,按照右端点从小到大排序

因此我们修改后,就不再存在有右端点小于当前位置 i i i的查询了,因此这样的修改是有效的。
所以我们要维护的就是每个数上一次出现的位置了。

代码
const int N = 1e6 + 10;
int n;
int tree[N];
void add(int i, int val) {while (i <= n) {tree[i] += val;i += lowbit(i);}
}
int query(int i) {int res = 0;while (i > 0) {res += tree[i];i -= lowbit(i);}return res;
}
int a[N];
struct node {int l, r, id;bool operator<(node& x) {if (r != x.r) return r < x.r;return l < x.l;}
}q[N];
int res[N], pre[N];
void solve() {cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];}int Q;cin >> Q;for (int i = 1; i <= Q; ++i) {int l, r;cin >> l >> r;q[i] = { l,r,i };}sort(q + 1, q + 1 + Q);int now = 1;for (int i = 1; i <= Q; ++i) {int l = q[i].l, r = q[i].r;for (int j = now; j <= r; ++j) {if (!pre[a[j]]) {pre[a[j]] = j;add(j, 1);}else {add(pre[a[j]], -1), add(j, 1);pre[a[j]] = j;}}now = r + 1;int s = query(r) - query(l - 1);res[q[i].id] = s;}for (int i = 1; i <= Q; ++i) cout << res[i] << "\n";}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(0);int t = 1;//cin >> t;while (t--) {solve();}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/429351.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C++初阶学习——探索STL奥秘——模拟实现list类

1、基本框架 list 由三个类构建而成: 节点类:每个节点必须的三部分(指向前一个节点的指针、指向后一个节点的指针、当前节点存储的数据) 迭代器类:此时的迭代器为双向迭代器&#xff0c;比较特殊&#xff0c;需要对其进行封装&#xff0c;如 it并非使迭代器单纯向后移动&…

BLE 设备丢包理解

前言 个人邮箱&#xff1a;zhangyixu02gmail.com在学习 BLE 过程中&#xff0c;总能听到 “丢包” 一词&#xff0c;但是我查阅资料又发现&#xff0c;有大佬说&#xff0c;ATT所有命令都是“必达”的&#xff0c;不存在所谓的“丢包”。而且我发现&#xff0c;在宣传 BLE 产品…

【如何在 Windows 10 主机上通过 VMware 安装 Windows 11 虚拟机,并共享主机网络】

环境说明 主机操作系统&#xff1a;Windows 10虚拟机操作系统&#xff1a;Windows 11虚拟机软件&#xff1a;VMware 步骤一&#xff1a;确保主机&#xff08;Windows 10&#xff09;网络连接正常 启动网络加速软件&#xff1a;在主机上启动软件&#xff0c;确保主机可以正常访…

分布式锁优化之 防死锁 及 过期时间的原子性保证(优化之设置锁的过期时间)

文章目录 1、AlbumInfoApiController --》testLock()2、AlbumInfoServiceImpl --》testLock()3、问题&#xff1a;可能会释放其他服务器的锁。 在Redis中设置一个名为lock的键&#xff0c;值为111&#xff0c;并且只有在该键不存在时才设置&#xff08;即获取锁&#xff09;。同…

Mistral AI 又又又开源了闭源企业级模型——Mistral-Small-Instruct-2409

就在不久前&#xff0c;Mistral 公司在开源了 Pixtral 12B 视觉多模态大模型之后&#xff0c;又开源了自家的企业级小型模型 Mistral-Small-Instruct-2409 &#xff08;22B&#xff09;&#xff0c;这是 Mistral AI 最新的企业级小型模型&#xff0c;是 Mistral Small v24.02 的…

【路径规划】自动泊车的 Simulink 模型

摘要 本文介绍了一个用于自主机器人路径规划和导航的 Simulink 模型&#xff0c;该模型结合了路径跟踪算法&#xff08;如 Pure Pursuit&#xff09;和动态机器人模型&#xff0c;实现了复杂环境中的路径跟随和导航控制。实验结果表明&#xff0c;模型能够在给定路径上精确控制…

QT快速安装使用指南

在Ubuntu 16.04上安装Qt可以通过多种方式进行。以下是使用Qt在线安装程序和apt包管理器的两种常见方法&#xff1a; 方法一&#xff1a;使用Qt在线安装程序 下载Qt在线安装程序 访问Qt官方网站&#xff1a;Try Qt | Develop Applications and Embedded Systems | Qt找到并下载…

初识ZYNQ——FPGA学习笔记15

一、ZYNQ简介 ZYNQ&#xff1a;Zynq-7000 All Programmable SoC&#xff08;APSoC&#xff09;&#xff0c;赛灵思公司&#xff08;AMD Xilinx&#xff09;推出的新一代全可编程片上系统 PS&#xff1a;Processing System&#xff0c;处理系统 PL&#xff1a;Program Logic&…

Linux:路径末尾加/和不加/的区别

相关阅读 Linuxhttps://blog.csdn.net/weixin_45791458/category_12234591.html?spm1001.2014.3001.5482 普通文件操作 首先说明这个问题只会出现在目录和符号链接中&#xff0c;因为如果想要索引普通文件但却在路径末尾加/则会出现错误&#xff0c;如例1所示。 # 例1 zhang…

Zotero(7.0.5)+123云盘同步空间+Z-library=无限存储文献pdf/epub电子书等资料

选择123云盘作为存储介质的原因 原因1&#xff1a; zotero个人免费空间大小&#xff1a;300M&#xff0c;如果zotero云端也保存文献pdf资料则远远不够 原因2&#xff1a; 百度网盘同步文件空间大小&#xff1a;1G123云盘同步文件空间大小&#xff1a;10G 第一台电脑实施步骤…

Hadoop的一些高频面试题 --- hdfs、mapreduce以及yarn的面试题

文章目录 一、HDFS1、Hadoop的三大组成部分2、本地模式和伪分布模式的区别是什么3、什么是HDFS4、如何单独启动namenode5、hdfs的写入流程6、hdfs的读取流程7、hdfs为什么不能存储小文件8、secondaryNameNode的运行原理9、hadoop集群启动后离开安全模式的条件10、hdfs集群的开机…

如何导入一个Vue并成功运行

注意1&#xff1a;要确保自己已经成功创建了一个Vue项目&#xff0c;创建项目教程在如何创建Vue项目 注意2&#xff1a;以下操作均在VS Code&#xff0c;教程在VS Code安装教程 一、Vue项目导入VS Code 1.点击文件&#xff0c;然后点击将文件添加到工作区 2. 选择自己的vue项…

有女朋友后,怎么养成贤内助?为自己找个好伴侣,为孩子找个好妈妈,为母亲找个好儿媳

有女朋友后&#xff0c;怎么养成贤内助&#xff1f;为自己找个好伴侣&#xff0c;为孩子找个好妈妈&#xff0c;为母亲找个好儿媳 时代背景女生有点作怎么办&#xff1f;大商家族的爱情观 时代背景 一块钱的东西&#xff0c;赋予俩块钱的意义&#xff0c;三块钱卖出去。 用商…

企业急于采用人工智能,忽视了安全强化

对主要云提供商基础设施上托管的资产的安全分析显示&#xff0c;许多公司为了急于构建和部署 AI 应用程序而打开安全漏洞。常见的发现包括对 AI 相关服务使用默认且可能不安全的设置、部署易受攻击的 AI 软件包以及不遵循安全强化指南。 这项分析由 Orca Security 的研究人员进…

Python爬虫使用实例-umei

优美图库 www.umei.cc BV1Ag41137re 1/获取资源 查看网站资源结构 多页&#xff0c;每个item只有一张图 多页&#xff0c;每个item都是一个图集 最大页码 内外层图集均有若干page。 通过尾页按钮确定pageNum&#xff1a; 2/发送请求 response requests.get(urlurl, header…

蓝桥杯【物联网】零基础到国奖之路:十. OLED

蓝桥杯【物联网】零基础到国奖之路:十.OLED 第一节 硬件解读第二节 MDK配置 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/fa7660b81be9407aa19c603561553db0.png)第三节 代码 第一节 硬件解读 OLED硬件知识: 第二节 MDK配置 第三节 代码 include头文件。 编…

Vue3 中组件传递 + css 变量的组合

文章目录 需求效果如下图所示代码逻辑代码参考 需求 开发一个箭头组件&#xff0c;根据父组件传递的 props 来修改 css 的颜色 效果如下图所示 代码逻辑 代码 父组件&#xff1a; <Arrow color"red" />子组件&#xff1a; <template><div class&…

VM-Ubantu中使用vscode头文件报错——解决办法

问题 系统中头文件明明存在但是却报错 解决方法 在报错的文件中点击&#xff0c;shift ctrl p选择Edit Configurations(JSON) 修改文件内容 原文件内容 修改之后的内容 {"configurations": [{"name": "Linux","includePath":…

https加密原理

以为http的数据都是以明文传送&#xff0c;会有很大的安全问题&#xff0c;所以出现的https协议。https就是在http协议的基础上增加了一个安全层&#xff0c;可以对数据进行加密和解密(例如SSL、TLS等)。 https加密解密的原理&#xff1a;证书非对称加密对称加密 在讲解原理前…

你了解system V的ipc底层如何设计的吗?消息队列互相通信的原理是什么呢?是否经常将信号量和信号混淆呢?——问题详解

前言&#xff1a;本节主要讲解消息队列&#xff0c; 信号量的相关知识。 ——博主主要是以能够理解为目的进行讲解&#xff0c; 所以对于接口的使用或者底层原理很少涉及。 主要的讲解思路就是先讨论消息队列的原理&#xff0c; 提一下接口。 然后讲解ipc的设计——这个设计一些…