一、树状数组
O ( l o g n ) O(logn) O(logn) ：单点修改、区间查询
与前缀和的区别：
- 前缀和是离线的，每次动态修改原数组某个元素，都需要重新求一遍前缀和，因此单点修改是 O ( n ) O(n) O(n) 的，区间查询则是 O ( 1 ) O(1) O(1)
- 树状数组是在线的，单点修改和区间查询都是 O ( l o g n ) O(logn) O(logn)
设下标从 1 1 1 开始
//树状数组的定义
t[x] = a[x - lowbit(x) + 1, x]
区间查询：求一段区间和
int query(int x)//[1, x]区间和
{
int res = 0;
for(int i = x; i > 0; i -= lowbit(i)) res += t[i];
return res;
}
单点修改：给某个数加上一个数
void add(int x, int v)//a[x] + v
{
for(int i = x; i <= n; i += lowbit(i)) t[i] += v;
}
lowbit
int lowbit(int x)
{
return x & -x;
}
二、线段树
线段树是一种二叉树，可以 O ( l o g n ) O(logn) O(logn) 维护区间的某种属性比如：区间和、区间最值
//线段树的定义
struct node
{
int l, r, v;
}t[4 * N];
//设根结点为1
//结点u的左孩子是2 * u，右孩子是2 * u + 1
下面以维护区间和为例：
树状数组能做的，线段树都能做，比如单点修改、区间查询
后序遍历建树
int a[N];//原数组
void build(int u, int l, int r)
{
t[u] = {l, r};
if(l == r)
{
t[u].v = a[l];
return;
}
int mid = (l + r) / 2;
build(2 * u, l, mid);
build(2 * u + 1, mid + 1, r);
pushup(u);
}
区间查询：求一段区间和
int query(int u, int l, int r)
{
if(t[u].l >= l && t[u].r <= r) return t[u].v;
int mid = (t[u].l + t[u].r) / 2;
int res = 0;
if(l <= mid) res += query(2 * u, l, r);
if(r > mid) res += query(2 * u + 1, l, r);
return res;
}
单点修改：给某个数加上一个数文章来源：https://www.toymoban.com/news/detail-826510.html
void modify(int u, int x, int v)//a[x] + v
{
if(t[u].l == t[u].r)
{
t[u].v += v;
return;
}
int mid = (t[u].l + t[u].r) / 2;
if(x <= mid) modify(2 * u, x, v);
else modify(2 * u + 1, x, v);
pushup(u);
}
pushup文章来源地址https://www.toymoban.com/news/detail-826510.html
void pushup(int u)
{
t[u].v = t[2 * u].v + t[2 * u + 1].v;
}
到了这里，关于【算法】树状数组和线段树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
