📟作者主页：慢热的陕西人
🌴专栏链接：力扣刷题日记
📣欢迎各位大佬👍点赞🔥关注🚓收藏，🍉留言
文章目录
- 树状数组和线段树
- 1.树状数组
- 1.1动态求连续区间和
- 1.2数星星
- 2.线段树
- 2.1动态求连续区间和
- 2.2数列区间最大值
树状数组和线段树
1.树状数组
1.1动态求连续区间和
链接：1264. 动态求连续区间和 - AcWing题库
三个核心函数：
lowbit(x):用于计算x的二进制的最后一个1在第几位(从1开始算)add(i, v):对树状数组中的第i个位置+vquery(i):计算原数组的s[i]
#include<iostream>
using namespace std;
const int N = 100010;
int a[N], tr[N];
int n, m;
int lowbit(int x)
{
return x & -x;
}
int 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()
{
cin >> n >> m;
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
//初始化，将原数组的每个值加到树状数组里即可
for(int i = 1; i <= n; ++i) add(i, a[i]);
//处理m次询问
for(int i = 0; i < m; ++i)
{
int k, x, y;
cin >> k >> x >> y;
if(k) add(x, y);
//计算区间和
else printf("%d\n", query(y) - query(x - 1));
}
return 0;
}
1.2数星星
链接：1265. 数星星 - AcWing题库
思路：因为输入的顺序，可以保证在当前星星之前的星星都是纵坐标小于当前星星的，那么我们只需要判断有多少个横坐标小于当前的星星的横坐标，那么就表示该星星是几等级的。因此我们只需要将横坐标的数据用一个树状数组维护起来，方便我们去修改和求值。
注意：因为树状数组的下标是从1开始的，那么我们每次读进来的树都要对横坐标+1；
#include<cstdio>
const int N = 32010;
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()
{
int n;
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;
}
2.线段树
操作一：单点修改O(logN)
递归直到叶节点，将对应的节点值修改，然后回溯的去算父节点的和(等于两个子节点的和)直到根节点。
操作二：区间查询O(logN)
区间查询就是问某一个区间的和是多少，递归和要查询的区间有交集的节点，若是当前的节点被区间完全包含那么就返回当前区间的值，否则继续向下递归。
主要函数
①pushup：
用子节点信息，更新当前节点信息。
②build：
在一段区间上初始化线段树
③modify：
修改操作
④query：
区间查询
2.1动态求连续区间和
相对复杂一些，注意处理边界和初始化问题，以及原数组从1开始填写。
#include<iostream>
const int N = 100010;
int w[N];
int n, m;
struct Node
{
int l, r;
int sum;
}tr[4 * N];
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);
//计算当前节点的sum值
pushup(u);
}
}
//修改x位置的值加v
void modify(int u, int x, int v)
{
//当遍历到叶节点，那么直接对该节点上的值+V
if(tr[u].l == tr[u].r) tr[u].sum += 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].sum;
//若是有交集，继续向下遍历
int mid = tr[u].l + tr[u].r >> 1;
int sum = 0;
if(l <= mid) sum = query(u << 1, l, r);
if(mid < r) sum += query(u << 1 | 1, l, r);
return sum;
}
int main()
{
scanf("%d%d", &n, &m);
//为了和线段树一致，从下标为1开始
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 != 0) modify(1, a, b);
else printf("%d\n", query(1, a, b));
}
return 0;
}
2.2数列区间最大值
链接：1270. 数列区间最大值 - AcWing题库
思路：我们只需要将原本节点存区间和的数据改为存区间最大值即可，然后其他代码非常类似。
但其实线段树的执行效率相对较低所以时间会慢一些。
#include<iostream>
#include<algorithm>
#include<climits>
using namespace std;
int n, m;
const int N = 100010;
int w[N];
struct Node
{
int l, r;
int maxv;
}tr[N * 4];
void build(int u, int l, int r)
{
//当build到叶节点的时候直接赋值
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);
tr[u].maxv = max(tr[u << 1].maxv, tr[u << 1 | 1].maxv);
}
}
int query(int u, int l, int r)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].maxv;
int mid = tr[u].l + tr[u].r >> 1;
int maxv = INT_MIN;
if(l <= mid) maxv = query(u << 1, l, r);
if(r > mid) maxv = max(maxv, query(u << 1 | 1, l, r));
return maxv;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1; i <=n; ++i) scanf("%d", &w[i]);
build(1, 1, n);
int l, r;
while(m--)
{
scanf("%d%d", &l, &r);
printf("%d\n", query(1, l, r));
}
return 0;
}
