一、树状数组核心原理全称Binary Indexed TreeBIT本质是利用数字二进制低位 1lowbit拆分区间用数组模拟树形结构实现单点修改(O(log n))前缀区间求和(O(log n))1. lowbit 是什么lowbit(x) x -x作用取出数字二进制最右侧的 1。 例 (x6(110))(-x)补码(6-62(10))lowbit22. 每个 tr [p] 存的是什么关键设原数组 (a[1---n])树状数组tr[] (tr[p]) 存储一段连续区间的和区间长度 (lowbit(p)) 区间范围([p-lowbit(p)1,p])举例子下标 1~8\(tr[1]\)lowbit1 → \([1,1]\)存 \(a_1\)\(tr[2]\)lowbit2 → \([1,2]\)存 \(a_1a_2\)\(tr[3]\)lowbit1 → \([3,3]\)存 \(a_3\)\(tr[4]\)lowbit4 → \([1,4]\)存 \(a_1a_2a_3a_4\)\(tr[5]\)lowbit1 → \([5,5]\)存 \(a_5\)\(tr[6]\)lowbit2 → \([5,6]\)存 \(a_5a_6\)\(tr[8]\)lowbit8 → \([1,8]\)全部和二、两大操作原理1. 单点更新 upd (pos, val)给原数组 (a[pos]) 加上 val向上更新所有包含 pos 的 tr 节点 循环pos lowbit(pos)沿途 tr 全部 val 原因所有区间右端点≥pos、覆盖 pos 的节点都要同步更新。//循环加lowbit恰好是覆盖自身的上位数2. 前缀查询 qry (pos)求 (a_1a_2...a_{pos})把 pos 不断减去 lowbit (pos)累加沿途 tr 值 例求前缀和到 6110pos6lowbit2加 tr [6]pos6-24pos4lowbit4加 tr [4]pos4-40 停止 总和 tr [6]tr [4]对应区间 ([5,6][1,4])正好 ([1,6])//减lowbit正好找到自己前面不覆盖的缺失区间三、区间求和 ([l,r])(sum(l,r) qry(r) - qry(l-1)) 前缀 1~r 减去 前缀 1~l-1得到中间一段和。通用树状数组板子单点修改 区间求和#includeiostream using namespace std; const int MAXN1e610; int tr[MAXN]; inline int lb(int x){return x-x;} // 单点加v void upd(int p,int v){ for(;pMAXN;plb(p)) tr[p]v; } // 1~p前缀和 int qry(int p){ int s0; for(;p;p-lb(p)) str[p]; return s; } // [l,r]区间和 int get(int l,int r){ return qry(r)-qry(l-1); }配套使用示例int main(){ int n,m; cinnm; for(int i1;in;i){ int x;cinx; upd(i,x); } while(m--){ int op,l,r; cinoplr; if(op1) upd(l,r); // l位置加r else coutget(l,r)\n; // 查询[l,r]和 } return 0; }拓展支持区间加、单点查询差分树状数组int tr[MAXN]; inline int lb(int x){return x-x;} void upd(int p,int v){ for(;pMAXN;plb(p)) tr[p]v; } void range_add(int l,int r,int v){ upd(l,v); upd(r1,-v); } int get(int p){ int s0; for(;p;p-lb(p)) str[p]; return s; }例题1静态使用树状数组基本性质Input 第一行一个整数T表示有T组数据。 每组数据第一行一个正整数NN50000,表示敌人有N个工兵营地接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人1ai50。 接下来每行有一条命令命令有4种形式 (1) Add i j,i和j为正整数,表示第i个营地增加j个人j不超过30 (2)Sub i j ,i和j为正整数,表示第i个营地减少j个人j不超过30; (3)Query i j ,i和j为正整数,ij表示询问第i到第j个营地的总人数; (4)End 表示结束这条命令在每组数据最后出现; 每组数据最多有40000条命令 Output 对第i组数据,首先输出“Case i:”和回车, 对于每个Query询问输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。#includecstdio #includecstring using namespace std; const int S50005; int tr[S]; int n,T; void rd(int x){ char chgetchar();int f1;x0; while(ch0||ch9){if(ch-)f-1;chgetchar();} while(ch0ch9)xx*10ch-0,chgetchar(); x*f; } int lb(int x){ return x-x; } void up(int p,int v){ for(;pn;plb(p))tr[p]v; } int qr(int p){ int s0; for(;p;p-lb(p))str[p]; return s; } int get(int l,int r){ return qr(r)-qr(l-1); } int main(){ rd(T); for(int cas1;casT;cas){ memset(tr,0,sizeof(tr)); rd(n); for(int i1;in;i){ int x;rd(x); up(i,x); }//树状数组的全部存入 printf(Case %d:\n,cas); char op[10]; while(scanf(%s,op)){ if(op[0]E) break; int i,j; rd(i),rd(j); if(op[0]A) up(i,j); else if(op[0]S) up(i,-j); else if(op[0]Q) printf(%d\n,get(i,j)); } } return 0; }2动态使用的树状数组这种动态数组不需要一次存入同时存入的过程自然是解答过程2-1有 N\(3\le N\le 20000\)名乒乓球选手住在一条东西走向的街道上把街道看作一条线段。 每名选手都有独一无二的技术排名。选手们经常互相切磋比赛。若两名选手想要比赛必须在其余选手中选出一名裁判并且比赛在裁判家举办。 有一条硬性规则裁判的技术排名不能同时高于、也不能同时低于两名参赛选手。 通俗说裁判水平必须介于两名选手之间一大一小两名选手需要步行到裁判家因为他们很懒两人步行总路程不能超过两名选手家之间的距离。 所有选手住址互不相同。只要两名参赛者不同或者裁判不同就视为两场不同的比赛。 求一共能举办多少场不同的比赛输入说明第一行输入整数 T\(1\le T\le 20\)代表测试数据组数。 之后 T 行每行描述一组测试数据 每组数据包含 \(N1\) 个整数 第一个数是选手人数 N 后面紧跟 N 个互不相同的整数 \(a_1,a_2\dots a_N\)代表从西到东依次每位选手的技术排名\(1\le a_i\le 100000\)。输出说明每组测试数据单独输出一行一个整数表示总共可以举办的比赛场次。#includecstdio #includecstring using namespace std; const int S100000; int tr[S10]; int lc[20010],rc[20010],a[20010]; int N; int lb(int x){ return x-x; } void up(int p,int v){ for(;pS;plb(p)) tr[p]v; } int qr(int p){ int s0; for(;p;p-lb(p)) str[p]; return s; } int main(){ int T; scanf(%d,T); while(T--){ scanf(%d,N); for(int i1;iN;i) scanf(%d,a[i]); memset(tr,0,sizeof(tr)); for(int i1;iN;i){ lc[i]qr(a[i]-1); up(a[i],1); }//数组存的是遍历读取时动态维护的每个数的出现次的前缀qr实现全部比目的数小的前缀和 memset(tr,0,sizeof(tr)); for(int iN;i1;i--){ rc[i]qr(a[i]-1); up(a[i],1); } long long ans0; for(int mid1;midN;mid){ int lgmid-1-lc[mid]; int rg(N-mid)-rc[mid]; ans1LL*lc[mid]*rg 1LL*lg*rc[mid]; } printf(%lld\n,ans); } return 0; }ps类似问题都可以如此解答如果值数非常大一次离散即可2-2有 N 个彩色小球从左至右排成一行从左数第 i 个小球的颜色为 (c_i)。现给出 Q 次询问。第 i 次询问内容从左第 (l_i) 个小球到第 (r_i) 个小球之间一共有多少种不同的颜色数据范围1e6输入所有数值均为整数。输入格式从标准输入按如下格式读入数据c₁ c₂ ⋯ c_N₁ r₁₂ r₂⋮l_Q r_Q输出要求共输出 Q 行第 i 行输出第 i 次询问的答案。#includecstdio #includealgorithm using namespace std; const int S500010; int c[S],res[S],lst[S],tr[S]; struct Q{ int l,r,id; }q[S]; void rd(int x){ char chgetchar();int f1;x0; while(ch0||ch9){if(ch-)f-1;chgetchar();} while(ch0ch9)xx*10ch-0,chgetchar(); x*f; } bool cmp(Q x,Q y){ return x.ry.r; } int lb(int x){ return x-x; } void upd(int p,int v){ for(;pS;plb(p))tr[p]v; } int qry(int p){ int s0; for(;p;p-lb(p))str[p]; return s; } int main(){ int n,m; rd(n),rd(m); for(int i1;in;i)rd(c[i]); for(int i1;im;i){ rd(q[i].l),rd(q[i].r); q[i].idi; } sort(q1,qm1,cmp); int p1; for(int i1;im;i){ for(;pq[i].r;p){ int xc[p]; if(lst[x])upd(lst[x],-1); upd(p,1); lst[x]p; } res[q[i].id]qry(q[i].r)-qry(q[i].l-1); } for(int i1;im;i)printf(%d\n,res[i]); return 0; }题目多次询问区间 ([l,r]) 有多少种不同颜色。 暴力做法每次遍历区间统计去重10^5数据直接超时。关键思路离线 右端点排序 树状数组维护 “每个颜色最后一次出现位置”核心转化我们规定 数组 \(mark[]\)若位置 i 是该颜色当前最后一次出现则 \(mark[i]1\)否则 \(mark[i]0\)。 那么区间 \([l,r]\) 内所有 mark 的和 区间内不同颜色总数。 原理同一种颜色只会在最靠右的位置贡献 1其余位置都是 0每种颜色恰好贡献 1 次。//右侧最后对应配套时离线按查询的右侧从小到大排序树状数组在这里承担什么工作树状数组用来维护 mark 数组提供两个操作单点修改某个位置 pos 数值 \(v\)v 只能是 1 或 \(-1\)区间求和快速算出 ([l,r]) 的总和分步完整流程步骤 1离线存储所有询问不能在线读一个查一个要把所有询问存下来记录三个信息 l左边界r右边界id询问原始编号最后按顺序输出答案struct Q{int l,r,id;} q[S];步骤 2把所有询问按右端点 r 从小到大排序目的用一个指针 p 从左向右逐个扩展到当前查询的 r不用每次重置只往前走只遍历一遍数组。//如果不按右端点排序需要每一次查询都要从头更新一遍到本次端点的所有mark否则会导致错误置0sort(q1,qm1,cmp); // cmpx.r y.r int p1; // 指针初始在1只递增不回头步骤 3遍历每个排好序的询问不断扩展右端点 p循环for(; p q[i].r; p)当前小球颜色 (x c[p])数组 (lst[x]) 记录颜色 x 上一次出现的下标。情况 1这个颜色之前出现过(lst[x]≠0)上一次的位置不再是该颜色最后出现的位置需要清除标记upd(lst[x], -1); // mark[lst[x]] - 1情况 2把当前位置标记为最新出现upd(p, 1); // mark[p] 1 lst[x] p; // 更新该颜色最后位置为p举个直观例子序列[2, 1, 2, 3]p1颜色 2lst [2]0 → upd (1,1)lst [2]1 mark[1,0,0,0]p2颜色 1lst [1]0 → upd (2,1)lst [1]2 mark[1,1,0,0]p3颜色 2lst [2]1 → upd (1,-1)再 upd (3,1)lst [2]3 mark[0,1,1,0]p4颜色 3lst [3]0 → upd (4,1)lst [3]4 mark[0,1,1,1]步骤 4当前右端点扩展完成计算当前询问答案树状数组求区间和 (sum qry(r) - qry(l-1))res[q[i].id] qry(q[i].r) - qry(q[i].l-1);把答案存到对应询问编号保证输出顺序不乱。步骤 5全部询问处理完按输入顺序输出答案for(int i1;im;i) printf(%d\n,res[i]);树状数组各函数在本题里的作用拆解lb(x)lowbit拆分二进制区间是树状数组基础upd(p, v)单点修改用来给 mark 数组增减 1旧位置减 1取消该位置的颜色贡献新位置加 1新增当前位置的颜色贡献qry(p)求 ([1,p]) 的 mark 前缀和(qry(r)-qry(l-1))快速求出 ([l,r]) 内总共有多少个 1即不同颜色数量时间复杂度说明数组遍历(O(N))每个位置只处理一次每个 upd、qry 操作(O(log N))