【算法】树状数组和线段树

一、树状数组

$O(logn)$ ：单点修改、区间查询

与前缀和的区别：

1. 前缀和是离线的，每次动态修改原数组某个元素，都需要重新求一遍前缀和，因此单点修改是 $O(n)$ 的，区间查询则是 $O(1)$
2. 树状数组是在线的，单点修改和区间查询都是 $O(logn)$

设下标从 $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(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;
}

单点修改：给某个数加上一个数

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

void pushup(int u)
{
   
    t[u].v = t[2 * u].v + t[2 * u + 1].v;
}