C语言详细讲解树状数组与线段树
时间：2022-12-24 13:50:18 | 栏目：C代码 | 点击：次
树状数组
动态求连续区间和
给定 n 个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列 [a,b] 的连续和。
输入格式
第一行包含两个整数 n 和 m，分别表示数的个数和操作次数。
第二行包含 n 个整数，表示完整数列。
接下来 m 行，每行包含三个整数 k,a,b （k=0，表示求子数列[a,b]的和；k=1，表示第 a 个数加 b）。
数列从 1 开始计数。
输出格式
输出若干行数字，表示 k=0 时，对应的子数列 [a,b] 的连续和。
数据范围
1≤n≤100000,
1≤m≤100000，
1≤a≤b≤n,
数据保证在任何时候，数列中所有元素之和均在 int 范围内。
输入样例：
10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8
输出样例：
11
30
35
这道题我最开始的想法就是只用前缀和，但后来发现只用前缀和会超时，因为数据范围
1≤n≤100000,
1≤m≤100000，
1≤a≤b≤n
//前缀和会超时
#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n,m;
int s1[N],s2[N];
int main ()
{
cin >> n >> m;
for(int i = 1 ; i <=n ; i++)
{
cin >> s1[i];
s2[i] = s2[i-1] + s1[i];
}
while(m--)
{
int k , a , b;
cin >> k >> a >> b;
if(k == 1)
{
s1[a] += b;
for(int i = 1 ; i <= n ; i++)
{
s2[i] = s2[i-1] + s1[i];
}
}
if(k == 0)
{
printf("%d\n", s2[b] - s2[a-1]);
}
}
}
然后我们再来分析一下树状数组是怎样的。
1、lowbit(x):返回x的最后一位1
2、add(x,v):在x位置加上v，并将后面相关联的位置也加上v
3、query(x):询问x的前缀和
时间复杂度 O(logn)
假设原序列为a，树状数组序列为c,那么是怎么由原序列得到树状数组序列的呢？(可以把c理解为a的前缀和序列，只是前缀和关系不像一般前缀和那样简单、线性)
1. 首先，将一维的树状数组序列c看成多层的序列，c[i]属于第几层，取决于i的二进制表示中最后一个1后面有几个0，有几个0就在第几层，显而易见,当i为奇数时，c[i]是在第0层的
因为lowbit(x)=2^k,k表示x的二进制表示后面有多少个0
（lowbit(n)求得n的二进制表示中最后一个1以及往后的0）
可以得到关系：c[x]=a[x?lowbit(x),x]
此关系描述了序列cc中每个元素是哪一段序列a中元素的和
2. 如何通过树状数组求前缀和？
由上面公式知道，想要求序列aa中11到xx的和，则应该是：
因而可得代码：
int res=0; for(int i=x;i>0;i-=lowbit(x)) res+=c[i]; return res;
如何通过树状数组进行单点修改？
这里我们给出一个结论：一个结点a[i]或c[i]的父结点为c[i+lowbit(i)]
所以当我们改变a[i]的值时，依次递归向上更新父结点的值即可。
代码：
a[x]+=v; for(int i=x;i<=n;i+=lowbit(i)) c[i]+=v;
最终代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int a[N], tr[N];//tr[N]表示图中的c[N];
int lowbit(int x)
{
return x & -x;
}
void add(int x, int v)
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}
int query(int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++ ) add(i, a[i]);
while (m -- )
{
int k, x, y;
scanf("%d%d%d", &k, &x, &y);
if (k == 0) printf("%d\n", query(y) - query(x - 1));
else add(x, y);
}
return 0;
}
最后再对比一下一般前缀和和树状数组：
可以看出在修改和查询操作占比差不多时，树状数组的效率更高
那么什么时候用树状数组，什么时候用一般前缀和算法呢？
这就要明白这两个算法的本质区别：
一般前缀和算法是离线算法，它不支持动态的改变单个元素的值，或者说改变单个元素值后，重新维护前缀和所花费的代价很大。
树状数组是在线算法，支持动态改变单个元素的值，以很小的代价动态维护前缀和。
所以当仅仅需要用到前缀和，不涉及动态的改变单个元素的值时，首选一般前缀和算法，否则就用树状数组。
数星星
天空中有一些星星，这些星星都在不同的位置，每个星星有个坐标。
如果一个星星的左下方（包含正左和正下）有 k 颗星星，就说这颗星星是 k 级的。
例如，上图中星星 5 是 3 级的（1,2,4 在它左下），星星 2,4 是 1 级的。
例图中有 1 个 0 级，2 个 1 级，1 个 2 级，1 个 3 级的星星。
给定星星的位置，输出各级星星的数目。
换句话说，给定 N 个点，定义每个点的等级是在该点左下方（含正左、正下）的点的数目，试统计每个等级有多少个点。
输入格式
第一行一个整数 N，表示星星的数目；
接下来 N 行给出每颗星星的坐标，坐标用两个整数 x,y 表示；
不会有星星重叠。星星按 y 坐标增序给出，y 坐标相同的按 x 坐标增序给出。
输出格式
N 行，每行一个整数，分别是 0 级，1 级，2 级，……，N?1 级的星星的数目。
数据范围
1≤N≤15000,
0≤x,y≤32000
输入样例：
5
1 1
5 1
7 1
3 3
5 5
输出样例：
1
2
1
1
0
这题看起来是二维的，但是实际上我们可以不用考虑y，因为星星按 y 坐标增序给出，y 坐标相同的按 x 坐标增序给出，所以我们只需要实时更新一下我们的树状数组就可以了。
如何更新？
这个题目本身就是一道利用前缀和思想做的题目。就和开头所说过的一样，只要求出有多少个星星的 x 值不小于该星星的 x 值就可以了，而这个过程就是利用的前缀和。
那让我们先用前缀和的思想来看一下这道题目。
假设现在存在一个前缀和数组 sum ，那么每当我们输入一个 x 的时候，我们都需要把 x 后面（包含x）的所有前缀和都加上 1 ，(因为在 x 后面的数都比 x 大，所以需要更新后面所有的前缀和)。然后我们在每次输入 x 的时候都实时更新一下前缀和并且实时计算一下我们的星星的等级就可以了。
这里为什么要强调实时计算星星等级的值呢？
因为我们这种操作方法是忽略了 y 的，之所以可以忽略 y 是因为题目输入的原因，所以其实我们是利用了这一特性来简化我们的算法的。其实如果这道题目输入的 y 并不按照不降原则来输入的话，那么这种算法就不对了。
现在说明一下为什么要实时计算，因为后面输入的 x 值很可能比我们前面输入的 x 值要小，因为数据输入的是按y不降输入的，而 x 可以是任意的，如果我们不实时计算，而是等到全部处理完再计算的话，会导致 “x 虽然比你大但是 y 比你小的情况”，而这种情况是显然不符合我们的题意的，所以说我们这种利用前缀和的算法是很特殊的，是仅仅针对于这个题目的。
能用到数据结构的算法的题目，往往是根据数据结构的特性来决定的。比如这个题目我们为什么要用树状数组来处理？是因为我们这里要运用前缀和，以及更新前缀和，而这恰好符合树状数组的特性，所以我们利用了它。
所以本题的思考思路总结应该是：
1、分析题目，通过输入特性判断解题方法
2、想想暴力解法怎么做？利用前缀和，每次用O(n)的时间复杂度更新前缀和
3、想想是否能优化？
4、想到树状数组优化
5、利用树状数组解决题目
请看代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 32010;
int n;
int tr[N], level[N];
int lowbit(int x)
{
return x & -x;
}
void add(int x)
{
for (int i = x; i < N; i += lowbit(i)) tr[i] ++ ;
}
int sum(int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
{
int x, y;
scanf("%d%d", &x, &y);
x ++ ;
level[sum(x)] ++ ;
add(x);
}
for (int i = 0; i < n; i ++ ) printf("%d\n", level[i]);
return 0;
}
线段树
动态求连续区间和
我们还是以动态求连续区间和为例
线段树基于分治思想
那么我们可以把每一个区间一分为二，这样就把整个区间变成了一棵树。
这样的话我们可以看一下两个操作，因为是树上，而且是一棵满二叉树，所以深度一定是O(logN)的。
1、pushup(u):用子节点信息来更新当前节点信息（把信息往上传递）
2、build(u,l,r):在一段区间上初始化线段树，其中u表示根结点，l表示左边界，r表示右边界
3、query(u,l,r):查询某段区间的和，其中u表示根结点，l表示左边界，r表示右边界
4、modify(u,x,v):修改操作，在u结点中，x位置加上v
我们来看一些基本的操作吧！
首先是上传的操作，线段树的意思就是用左右子树更新根节点。
怎么写呢？
这个的话我们结合着拿到题写吧。
就是单点修改，区间查询。
线段树的话一般使用结构体维护。
结构体里想要啥有啥放进去就行了。
struct Node
{
int l, r;//左右端点区域
int sum;//各种查询变量存储区域
//最后还有个懒标记区域，一般在区间修改时使用。
}tr[N * 4];//4倍空间
那么的话pushup的操作就是用左右两边的区间更新总区间。
这个的话很简单，大区间等于小区间的和。
void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
然后就是建树操作，在最开始需要把树“建造出来”。
这个可以直接递归建立树。
这个的话可以分治处理。
void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, r, w[r]};
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
然后就是变化操作和查询操作。
变化操作就是直接搜就行了。
void modify(int u, int x, int v)
{
if (tr[u].l == x && tr[u].r == x) tr[u] = {x, x, v;
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
}
然后是查询操作。
这个也不难。
就可以直接判断区间。
int query(int u, int l, int r)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].v;
int mid = tr[u].l + tr[u].r >> 1;
int v = 0;
if(l <= mid) v = query(u << 1, l, r);
if(r > mid) v = max(v, query(u << 1 | 1, l, r));
return v;
}
线段树的思想上面已经说完了，那么就是代码了：
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int w[N];
struct Node
{
int l, r;
int sum;
}tr[N * 4];
void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u, int l, int r)
{
if(l == r) tr[u] = {l, r, w[r]};
else
{
tr[u] = {l, r};
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void change(int u, int x, int v)
{
if(tr[u].l == x && tr[u].r == x)
{
tr[u] = {x, x, tr[u].sum + v};
}
else
{
int mid = (tr[u].l + tr[u].r) >> 1;
if(x <= mid) change(u << 1, x, v);
else change(u << 1 | 1, x, v);
pushup(u);
}
}
int query(int u, int l, int r)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
else
{
int mid = (tr[u].l + tr[u].r) >> 1;
if(r <= mid) return query(u << 1, l, r);
else if(l > mid) return query(u << 1 | 1, l, r);
else
{
int left = query(u << 1, l, r);
int right = query(u << 1 | 1, l, r);
int ans;
ans = left + right;
return ans;
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++)
{
cin >> w[i];
}
build(1, 1, n);
while(m --)
{
int op, l, r;
cin >> op >> l >> r;
if(op == 0)
{
cout << query(1, l, r) << endl;
}
else
{
change(1, l, r);
}
}
return 0;
}
数列区间最大值
输入一串数字，给你 M 个询问，每次询问就给你两个数字 X,Y，要求你说出 X 到 Y 这段区间内的最大数。
输入格式
第一行两个整数 N,M 表示数字的个数和要询问的次数；
接下来一行为 N 个数；
接下来 M 行，每行都有两个整数 X,Y。
输出格式
输出共 M 行，每行输出一个数。
数据范围
1≤N≤105,
1≤M≤106,
1≤X≤Y≤N,
数列中的数字均不超过231?1
输入样例：
10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8
输出样例：
5
8
这题和动态求连续区间和差不多，直接套就可以了。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int w[N];//数值
struct Node
{
int l,r,maxv;// 把记录区间和的sum换成了记录区间最大值的maxv
}tr[4*N];//二叉树 n+n/2+n/4..=2n 加底层最大 =4n
int pushup(int u)
{
return tr[u].maxv = max (tr[u<<1].maxv,tr[u<<1|1].maxv);//更新数据 两个子树当中取最大
}
void build(int u,int l,int r)//初始化线段树 u序号 lr具体范围
{
if(l==r)tr[u]={l,r,w[r]};//如果只有一个数据 即最大是当前数据
else
{
tr[u]={l,r};
int mid=l+r>>1;//初始化二叉树 只与结构有关 与本身数据无关 所以mid = l+r>>1
build(u<<1,l,mid),build(u<<1|1,mid+1,r);//递归找两个子树
pushup(u);//当前的最大值等于两个子树间的最大值
}
}
int query(int u,int l,int r)//u序号 lr要查找的范围
{
if(l<=tr[u].l&&tr[u].r<=r)return tr[u].maxv;//如果要查找的范围包含当前范围则直接返回最值
else
{
int maxv=0;
int mid=tr[u].l+tr[u].r>>1;//与本身数据有关 做中间值 用于找包含部分
if(l<=mid)maxv=query(u<<1,l,r);//如果左边有包含部分 则更新左子树
if(r>=mid+1)maxv=max(maxv,query(u<<1|1,l,r));//如果右边有包含部分 则更新右子树
return maxv;//当前maxv实际是由底层逐层比对返回的在指定区域内的最大值
}
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
build(1,1,n);//初始化线段树
int x,y;
while(m--)
{
scanf("%d%d",&x,&y);
printf("%d\n",query(1,x,y));
}
return 0;
}