🌟1.树状数组
解题思路:
1.构造树状数组的核心函数lowbit(x),add(x, k), query(x),其中迭代查找lowbit获取最低二进制1所代表的10进制数实现自动化
2.构建、更改树状数组调用add(x, k)即可
3.查询区间和调用query(x)-query(y - 1)类比前缀和求法
时间复杂度👇
查询、更新均为O(logN)
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < b; i++)
const int N = 1e5 + 10;
int a[N],tr[N]; //原数组和对应的树状数组 lowbit相对应所在的层数
int n, m;
//核心函数1.lwobit
int lowbit(int x) //获取当前数组下标对应二进制数最低位
{
return x & -x ; //原数字 与 反码 + 1(PC中补码 用负数表示) 最低位1所代表的10进制数
}
//核心函数2.query
int query(int x) //查找截止1...x数组内的前缀和
{
int res = 0;
for(int i = x; i; i -= lowbit(i)) //踩坑:递归减去自己二进制最低位1代表的10进制数 -> lowbit(i)
res += tr[i];
return res;
}
//核心函数3.add(动态维护树状数组)
void add(int x, int k) //增加某个数字 -> 树状数组前文相关联的数字全部都增加
{
// a[x] += k; 注意原数组不进行改变,只改变树状数组即可
for(int i = x; i <= n; i += lowbit(i))
tr[i] += k;
}
int main()
{
scanf("%d%d", &n, &m);
rep(i, 1, n + 1) scanf("%d", &a[i]);
//1.初始化树状数组,部分连续前缀和的存储
rep(i, 1, n + 1) add(i, a[i]);
while(m -- )
{
int k, x, y;
scanf("%d%d%d", &k, &x, &y);
//2.树状数组的query、add函数调用
if(k == 0)
printf("%d\n", query(y) - query(x - 1)); //查询前缀和(树状数组上面)
else
add(x, y); //第x个数字,加y,O(logN)维护树状数组
}
return 0;
}
🌟2.线段树
解题思路:
1.构造线段树的核心函数build(p, l, r)、update(p, x, k)、query(p, x, y),最后的结算和更新都是利用回溯的过程,即”归”
2.构建、更改线段树调用build(p, l, r)、update(p, x, k)即可
3.查询区间和调用query(p, x, y)即可,相较于树状数组方便点儿,但整体还是树状数组好呀
重点:
理解线段树动态建树、更新、查询的递归过程。
时间复杂度👇
平均O(logN)
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < b; i++)
#define ls p<<1
#define rs p<<1 | 1
const int N = 1e5 + 10;
int a[N];
int n, m;
struct node{
int l, r, sum;
} tr[4 * N]; //线段树的存储空间 始终小于 4 * N
void build(int p, int l, int r) //O(logN)
{
tr[p] = {l, r, a[r]};
if(l == r) //递归出口
return ;
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
//回溯结算 区间和
tr[p].sum = tr[ls].sum + tr[rs].sum;
}
void update(int p, int x, int k) //O(logN)
{
if(tr[p].l == x && tr[p].r == x)
{
tr[p].sum += k;
return ;
}
int mid = tr[p].l + tr[p].r >> 1;
if(x <= mid) update(ls, x, k); //只需更新一半儿区间即可
else update(rs, x, k);
tr[p].sum = tr[ls].sum + tr[rs].sum; //更新区间和
}
int query(int p, int x, int y) //最坏情况下O(N)懒标记可以优化为O(logN),最好O(logN)
{
if(x <= tr[p].l && y >= tr[p].r)
return tr[p].sum;
int mid = tr[p].l + tr[p].r >> 1;
int res = 0;
if(x <= mid) res += query(ls, x, y);
if(y > mid) res += query(rs, x, y);
return res; //返回递归查询的区间和
}
int main()
{
scanf("%d%d", &n, &m);
rep(i, 1, n + 1)
cin >> a[i];
build(1, 1, n); //构造线段树
while (m -- ){
int k, x, y;
scanf("%d%d%d", &k, &x, &y);
if(k == 0)
cout << query(1, x, y) << endl;
else
update(1, x, y);
}
return 0;
}