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

一、树状数组

O

(

l

o

g

n

)

O(logn)

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

与前缀和的区别：

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

单点修改：给某个数加上服务器托管网一个数

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;
}

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: 时序预测 | MATLAB实现ICEEMDAN-SSA-GRU、ICEEMDAN-GRU、SSA-GRU、GRU时间序列预测对比

时序预测 | MATLAB实现ICEEMDAN-SSA-GRU、ICEEMDAN-GRU、SSA-GRU、GRU时间序列预测对比 目录 时序预测 | MATL服务器托管网AB实现ICEEMDAN-SSA-GRU、ICEEMDAN-GRU、SSA-GRU、GRU…