企业官网建设流程全解析

一、树状数组核心原理

全称Binary Indexed Tree（BIT），本质是利用数字二进制低位 1（lowbit）拆分区间，用数组模拟树形结构，实现：

1. 单点修改：(O(log n))
2. 前缀区间求和：(O(log n))

1. lowbit 是什么

lowbit(x) = x & -x，作用：取出数字二进制最右侧的 1。 例： (x=6(110))，(-x)补码，(6&-6=2(10))，lowbit=2

2. 每个 tr [p] 存的是什么（关键）

设原数组 (a[1---n])，树状数组tr[]： (tr[p]) 存储一段连续区间的和，区间长度 = (lowbit(p)) 区间范围：([p-lowbit(p)+1,p])

举例子（下标 1~8）：

• \(tr[1]\)：lowbit=1 → \([1,1]\)，存 \(a_1\)
• \(tr[2]\)：lowbit=2 → \([1,2]\)，存 \(a_1+a_2\)
• \(tr[3]\)：lowbit=1 → \([3,3]\)，存 \(a_3\)
• \(tr[4]\)：lowbit=4 → \([1,4]\)，存 \(a_1+a_2+a_3+a_4\)
• \(tr[5]\)：lowbit=1 → \([5,5]\)，存 \(a_5\)
• \(tr[6]\)：lowbit=2 → \([5,6]\)，存 \(a_5+a_6\)
• \(tr[8]\)：lowbit=8 → \([1,8]\)，全部和

二、两大操作原理

1. 单点更新 upd (pos, val)

给原数组 (a[pos]) 加上 val，向上更新所有包含 pos 的 tr 节点： 循环：pos += lowbit(pos)，沿途 tr 全部 +val 原因：所有区间右端点≥pos、覆盖 pos 的节点都要同步更新。

//循环加lowbit恰好是覆盖自身的上位数

2. 前缀查询 qry (pos)，求 (a_1+a_2+...+a_{pos})

把 pos 不断减去 lowbit (pos)，累加沿途 tr 值： 例：求前缀和到 6（110）

1. pos=6，lowbit=2，加 tr [6]，pos=6-2=4
2. pos=4，lowbit=4，加 tr [4]，pos=4-4=0 停止 总和 = 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，得到中间一段和。

通用树状数组板子（单点修改 + 区间求和）

#include<iostream> using namespace std; const int MAXN=1e6+10; int tr[MAXN]; inline int lb(int x){return x&-x;} // 单点加v void upd(int p,int v){ for(;p<MAXN;p+=lb(p)) tr[p]+=v; } // 1~p前缀和 int qry(int p){ int s=0; for(;p;p-=lb(p)) s+=tr[p]; return s; } // [l,r]区间和 int get(int l,int r){ return qry(r)-qry(l-1); }

配套使用示例

int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++){ int x;cin>>x; upd(i,x); } while(m--){ int op,l,r; cin>>op>>l>>r; if(op==1) upd(l,r); // l位置加r else cout<<get(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(;p<MAXN;p+=lb(p)) tr[p]+=v; } void range_add(int l,int r,int v){ upd(l,v); upd(r+1,-v); } int get(int p){ int s=0; for(;p;p-=lb(p)) s+=tr[p]; return s; }

例题

1，静态使用树状数组（基本性质）

Input 第一行一个整数T，表示有T组数据。 每组数据第一行一个正整数N（N<=50000）,表示敌人有N个工兵营地，接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人（1<=ai<=50）。 接下来每行有一条命令，命令有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为正整数,i<=j，表示询问第i到第j个营地的总人数; (4)End 表示结束，这条命令在每组数据最后出现; 每组数据最多有40000条命令 Output 对第i组数据,首先输出“Case i:”和回车, 对于每个Query询问，输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。

#include<cstdio> #include<cstring> using namespace std; const int S=50005; int tr[S]; int n,T; void rd(int &x){ char ch=getchar();int f=1;x=0; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); x*=f; } int lb(int x){ return x&-x; } void up(int p,int v){ for(;p<=n;p+=lb(p))tr[p]+=v; } int qr(int p){ int s=0; for(;p;p-=lb(p))s+=tr[p]; return s; } int get(int l,int r){ return qr(r)-qr(l-1); } int main(){ rd(T); for(int cas=1;cas<=T;cas++){ memset(tr,0,sizeof(tr)); rd(n); for(int i=1;i<=n;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 行，每行描述一组测试数据： 每组数据包含 \(N+1\) 个整数： 第一个数是选手人数 N； 后面紧跟 N 个互不相同的整数 \(a_1,a_2\dots a_N\)，代表从西到东依次每位选手的技术排名（\(1\le a_i\le 100000\)）。

输出说明

每组测试数据单独输出一行一个整数，表示总共可以举办的比赛场次。

#include<cstdio> #include<cstring> using namespace std; const int S=100000; int tr[S+10]; int lc[20010],rc[20010],a[20010]; int N; int lb(int x){ return x&-x; } void up(int p,int v){ for(;p<=S;p+=lb(p)) tr[p]+=v; } int qr(int p){ int s=0; for(;p;p-=lb(p)) s+=tr[p]; return s; } int main(){ int T; scanf("%d",&T); while(T--){ scanf("%d",&N); for(int i=1;i<=N;i++) scanf("%d",&a[i]); memset(tr,0,sizeof(tr)); for(int i=1;i<=N;i++){ lc[i]=qr(a[i]-1); up(a[i],1); }//数组存的是遍历读取时，动态维护的每个数的出现次的前缀，qr实现全部比目的数小的前缀和 memset(tr,0,sizeof(tr)); for(int i=N;i>=1;i--){ rc[i]=qr(a[i]-1); up(a[i],1); } long long ans=0; for(int mid=1;mid<=N;mid++){ int lg=mid-1-lc[mid]; int rg=(N-mid)-rc[mid]; ans+=1LL*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 次询问的答案。

#include<cstdio> #include<algorithm> using namespace std; const int S=500010; int c[S],res[S],lst[S],tr[S]; struct Q{ int l,r,id; }q[S]; void rd(int &x){ char ch=getchar();int f=1;x=0; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); x*=f; } bool cmp(Q x,Q y){ return x.r<y.r; } int lb(int x){ return x&-x; } void upd(int p,int v){ for(;p<S;p+=lb(p))tr[p]+=v; } int qry(int p){ int s=0; for(;p;p-=lb(p))s+=tr[p]; return s; } int main(){ int n,m; rd(n),rd(m); for(int i=1;i<=n;i++)rd(c[i]); for(int i=1;i<=m;i++){ rd(q[i].l),rd(q[i].r); q[i].id=i; } sort(q+1,q+m+1,cmp); int p=1; for(int i=1;i<=m;i++){ for(;p<=q[i].r;p++){ int x=c[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 i=1;i<=m;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 数组，提供两个操作：

1. 单点修改：某个位置 pos 数值 \(+v\)（v 只能是 1 或 \(-1\)）
2. 区间求和：快速算出 ([l,r]) 的总和

分步完整流程

步骤 1：离线存储所有询问

不能在线读一个查一个，要把所有询问存下来，记录三个信息： l：左边界，r：右边界，id：询问原始编号（最后按顺序输出答案）

struct Q{int l,r,id;} q[S];

步骤 2：把所有询问按右端点 r 从小到大排序

目的：用一个指针 p 从左向右逐个扩展到当前查询的 r，不用每次重置，只往前走，只遍历一遍数组。

//如果不按右端点排序，需要每一次查询都要从头更新一遍到本次端点的所有mark，否则会导致错误置0

sort(q+1,q+m+1,cmp); // cmp：x.r < y.r int p=1; // 指针初始在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]

1. p=1，颜色 2：lst [2]=0 → upd (1,1)，lst [2]=1 mark=[1,0,0,0]
2. p=2，颜色 1：lst [1]=0 → upd (2,1)，lst [1]=2 mark=[1,1,0,0]
3. p=3，颜色 2：lst [2]=1 → upd (1,-1)，再 upd (3,1)，lst [2]=3 mark=[0,1,1,0]
4. p=4，颜色 3：lst [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 i=1;i<=m;i++) printf("%d\n",res[i]);

树状数组各函数在本题里的作用拆解

1. lb(x)：lowbit，拆分二进制区间，是树状数组基础
2. upd(p, v)：单点修改，用来给 mark 数组增减 1
   • 旧位置减 1：取消该位置的颜色贡献
   • 新位置加 1：新增当前位置的颜色贡献
3. qry(p)：求 ([1,p]) 的 mark 前缀和
4. (qry(r)-qry(l-1))：快速求出 ([l,r]) 内总共有多少个 1，即不同颜色数量

时间复杂度说明

1. 数组遍历：(O(N))，每个位置只处理一次
2. 每个 upd、qry 操作：(O(log N))