树状数组与线段树
更新: 12/19/2024 字数: 0 字 时长: 0 分钟
区别：线段树可以完全解决树状数组的问题，但树状数组代码复杂度与时间复杂度明显低于线段树
树状数组
时间复杂度：O（logn）
作用
1.动态给区间中某个位置上的数加上一个数（单点修改）
2.在logn的时间复杂度下快速求前缀和（区间查询）
在此基础上加上差分即可实现：
1.区间修改
2.单点查询
特点
1.线段树的每个节点代表一个区间 2.线段树具有唯一的根节点，代表的区间是整个统计范围，如[1 , N]. 3.线段树的每个叶子节点代表一个长度位一的元区间[x,x]. 4.对于每个内部节点[l,r],它的左儿子是[l ,mid],右儿子[mid + 1 , r], 其中 mid = (l + r) / 2 (下取整)
结构
1.下标的二进制表示的末尾有几个零该下标就表示第几层 ——>lowbit(x)
2.每一层表示其前面直到第一个与其处于相同的层数间所有小于其层数的下标上的数的和
写法
给定 n 个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列 [a,b]的连续和。
输入
第一行包含两个整数 n 和 m，分别表示数的个数和操作次数。
第二行包含 n个整数，表示完整数列。
接下来 m行, 每行包含三个整数 k,a,b （k=0，表示求子数列[a,b]的和；k=1，表示第 a 个数加 b）。
数列从 1开始计数。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int n,m;
int a[N],tr[N]; //a为原数组，tr为树状数组
int lowbit(int x){
return x&-x; //通过与自己的负数形式取按位和可以返回末尾二进制数的0的个数
}
void add(int x,int v){
for(int i=x;i<=n;i+= lowbit(i)) tr[i]+=v;
}
//对原数组的第x位加上v后树状数组发生的变化
//由于树状数组的特性，一个数变化只会影响其后面所有大于他的层数的下标上的数，所以我们只需要改变i+= lowbit(i)上的数即可
//时间复杂度为O(logn)
int query(int x){
int res=0;
for(int i=x;i;i-= lowbit(i)) res+=tr[i];
return res;
}
//表示原数组（0，y]上的区间和
//由于树状树状的特性，我们只需要将i-lowbit(x)上的数加起来即可
//该区间和为左开右闭
//时间复杂度为O(logn)
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) add(i,a[i]); //初始化的过程是假定原数组全部都是0，然后通过对每一个位上加上一个特定的数来构建
while(m--){
int k,x,y;
cin>>k>>x>>y;
if(k==1) add(x,y);
else cout<<query(y)- query(x-1)<<"\n";
}
}与前缀和的区别
前缀和的本质是在输入原数组的同时便创造出一个前缀和数组，之后通过打表的方式来得到任何一个区间的前缀和
由于是打表的原因，前缀和的时间复杂度低达惊人的O(1)
而树状数组数组本身是通过自身独特的结构性质来完成的区间计算，因此时间复杂度为O(logn)，在这一方面上树状数组的效率明显低于前缀和
但题目若涉及到频繁的对原数组/前缀和数组进行改动（动态求前缀和/原数组处于时刻变化中）借由树状数组的特性，我们可以通过O(logn)的时间复杂度来完成这一操作
而前缀和若想要完成这一操作，则只能通过暴力完成，时间复杂度高达惊人的O(logn)
线段树
结构
完全二叉树
对于每一个节点，我们使用一个结构体进行存储，每个结构体中存入两组数据：
1.该节点代表的区间
2.题目中需要使用的数据
对于一个根结点（l,r），其左右两个子树的根结点代表的区间为(l,mid),(mid+1,r) mid=l+r/2
在存储时，线段树使用堆存储的方式，即一颗线段树的根的编号为1，设任意不为根的节点编号为x，则该节点1的父节点为x/2(x>>1)，他的两个子节点分别为2x（x<<1）与2x+1（x<<1|1）
作用
在时间复杂度为O(logn)的情况下完成以下操作
1.单点修改 ：对原数组某一个点完成修改后仍可使用线段树完成查询操作
2.区间修改 ：对原数组某一个区间完成修改后仍可使用线段树完成查询操作
3.区间查询 ： 包括但不限于即区间求和，求区间 max，求区间 min，区间 gcd，对于不同的查询的要求，线段树中存储的数据存在一定的差异
思想
线段树基于分治思想，将一个区间无限下分到每个区间的长度只有1（叶子节点）
单点修改：当我们要对一个单点进行修改时，只需要修改线段树中包含该点的区间的节点即可
区间查询：当我们查询一个区间时只需通过线段树中最少的节点数量去拼抽出这个节点即可
写法
给定 n 个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列 [a,b]的连续和。
输入
第一行包含两个整数 n 和 m，分别表示数的个数和操作次数。
第二行包含 n个整数，表示完整数列。
接下来 m行, 每行包含三个整数 k,a,b （k=0，表示求子数列[a,b]的和；k=1，表示第 a 个数加 b）。
数列从 1开始计数。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100010;
int n,m;
int w[N];//记录原数组
struct Node{
int l,r; //存入该节点代表的区间
int sum; //由于本题求区间和，所以此处还要先求一个sum
}tr[4*N]; //跟据完全二叉树的理论，我们可知在最多情况下线段树最多会存有4N个节点
void push_up(int u){ //此处的参数u表示该节点的下标
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
//线段树的建立是由叶子节点向上建立的
//因此根结点的数据可以由他的两个子树的根结点的数据来推出
}
void build(int u,int l,int r){ //u:节点编号，l：左区间，r：右区间
if(l==r) tr[u]={l,r,w[l]};
//设置递归终点（递归可以实现我们从下向上建树的需求）
//当l=r时，我们直接存入数据即可
else{
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid); //建立左子树
build(u<<1|1,mid+1,r);//建立右子树
//此时左右子树已完成建立
push_up(u); //通过左右子树的数据为当前节点赋值
}
}
int query(int u,int l,int r){ //查询操作从上向下查询，直到找到我们需要的数
if(l<=tr[u].l&&tr[u].r<=r) return tr[u].sum; //规定区间第一次大于该区间，就说明这个是我们需要的子区间中处于最上层的数据之一
int mid=tr[u].l+tr[u].r>>1; //若不是子区间，则向下继续查询
int sum=0;
if(l<=mid) sum+= query(u<<1,l,r);//若左子树代表的区间与代求区间区间存在交集，则加上
if(r>=mid+1) sum+= query(u<<1|1,l,r);//若左右子树代表的区间与代求区间区间存在交集，则加上
return sum;
}
void modify(int u,int x,int v){ //u仍为根结点，x为指定位置，v为要加上的值
if(tr[u].l==tr[u].r) tr[u].sum+=v; //当区间为1时说明到达叶子节点，此时直接加上即可
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);
push_up(u); //通过新的左右子树的根结点的数据来更新自己
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
build(1,1,n);
while(m--){
int k,a,b;
scanf("%d%d%d",&k,&a,&b);
if(!k)printf("%d\n", query(1,a,b));
else modify(1,a,b);
}
}