算法1
树状数组
简单的来说 ,树状数组 是一种 偶变 奇数不变,更变 看 二进制 0
在一个数组里边,奇数放的是只有它自己,而偶数里面 ,看他能整除多少个二,它能整出的2越多,它‘背负’的 ‘东西’
也就越多
这种2得倍数 越多 背负 越多的核心操作 就是 通过lowbit 操作 来寻找这种关联对应下的位置的
具体理解 看下下面那张 截图 和代码实现
核心操作只有 3 个:
- lowbit操作 -> 用来 寻找到那些 对应的 关联着的 位置
- add操作 -> 用来更新数值
- query操作 -> 用来求前缀和,查询
对 add 和 query中 通过lowbit操作寻找到那些关联位置有疑惑的话可以看下下面这张截图
C++ 代码
#include<iostream>
using namespace std;
const int N=1e5+5;
#define endl '\n'
void fast(){
std::ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
}
int m,n;
int A[N],tree[N];
int lowbit(int x){return x&-x;}
void add(int x,int v){
for(int i=x;i<=n;i+= lowbit(i)){
tree[i]+=v;
}
}
int query(int x){
int res=0;
for(int i=x;i>0;i-= lowbit(i)){
res+=tree[i];
}
return res;
}
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]);//初始化
int k,a,b;
while (m--){
cin>>k>>a>>b;
if(k==0)cout<<query(b)- query(a-1)<<endl;
else add(a,b);
}
}
算法2
线段树
线段树,算是 在用结构体定义的数组里面
结构体中包含 一个权值,一个区间 的 l 起点 和 r终点
将1作为 根节点, 将每个节点的子节点 甩到 现在的节点 * 2(左孩子) 和 现在的节点 *2+1(右孩子)对应的地方去
核心操作其实 也是围绕这种结构进行操作
三个核心操作
build 初始化整个体系
query 查询
modify 更新
C++ 代码
#include<iostream>
using namespace std;
const int N=1e5+5;
#define endl '\n'
void fast(){
std::ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
}
int n,m,k,a,b;
int A[N];
struct node{
int l, r;
int sum;
}tree[N*4];
void build(int u,int l,int r){
tree[u]={l,r};
if(l==r) { tree[u].sum = A[l];return; }
int mid=l+r>>1;
build(u<<1,l,mid);//左区间
build(u<<1|1,mid+1,r);//右边区间
tree[u].sum=tree[u<<1].sum+tree[u<<1|1].sum;
}
void modify(int u,int x,int v){
if(tree[u].l==tree[u].r) { tree[u].sum += v; return;}
int mid=tree[u].l+tree[u].r>>1;
if(x<=mid)modify(u<<1,x,v);//看x在哪个区间内
else modify(u<<1|1,x,v);
tree[u].sum+=v;
}
int query(int u,int l,int r){
if(l<=tree[u].l&&r>=tree[u].r)return tree[u].sum;
//如果包含 u 对应的区间,就直接返回
int mid=tree[u].l+tree[u].r>>1;
int res=0;
if(mid>=l)res+=query(u<<1,l,r);//如果 u的 左 区间包含了 目标区间的一部分,就进去寻找
if(mid+1<=r)res+=query(u<<1|1,l,r);
return res;
}
int main(){
fast();
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>A[i];
build(1,1,n);//初始化
while (m--){
cin>>k>>a>>b;
if(k==0)cout<<query(1,a,b)<<endl;
else modify(1,a,b);
}
return 0;
}