基本原理树状数组

树状数组是一种基于位操作的数据结构，常用于解决动态区间最值问题。其核心原理基于以下性质：每个节点代表一个区间，该区间的最大值可能来自其左子节点。通过将元素依次添加到树状数组的尾部，树状数组可以在O(log n)时间内完成插入和查询操作。

树状数组的建立

树状数组的推送操作如下：

void push(int pos) {    int i, lb = lowbit(pos);    c[pos] = a[pos];    for (i = 1; i < lb; i++) {        c[pos] = max(c[pos], c[pos - i]);    }}

该函数在指定位置插入元素，并向上更新路径上的每个父节点的最大值。

树的维护

更新操作如下：

void update(int pos, int v) {    int i, lb;    c[pos] = a[pos] = v;    lb = lowbit(pos);    for (i = 1; i < lb; i++) {        c[pos] = max(c[pos], c[pos - i]);    }    for (pos = pos + lowbit(pos); pos <= n; pos += lowbit(pos)) {        if (c[pos] < c[pos - lowbit(pos)]) {            c[pos] = c[pos - lowbit(pos)];        } else {            break;        }    }}

区间查询

查询区间最值的逻辑如下：

确定当前区间的左右边界。

开始遍历区间的右半部分，如果当前节点的左子树区间完全在查询区间内，则直接比较当前节点的值。

否则，递归进入左子树，继续查询。

int query(int x, int y) {    int res = -1;    while (x <= y) {        int nx = y - lowbit(y) + 1;        if (nx >= x) {            res = max(res, c[y]);            y = nx - 1;        } else {            res = max(res, a[y]);            y--;        }    }    return res;}

树状数组的特点

高效性：每次操作时间复杂度为O(log n)。

数据结构灵活：可以在线性时间内插入数据。

适用场景：适合需要频繁插入尾部数据且需要查询不同区间最值的问题。

核心代码

const int maxn = 1e6 + 5, maxe = 1e6 + 5;int n, m;int N = maxn;int a[maxn], c[maxn];inline int lowbit(int x) {    return x & -x;}inline int fa(int p) {    return p + lowbit(p);}inline int left(int p) {    return p - lowbit(p);}inline int g(int a, int b) {    return a > b ? a : b;}void update_by_child(int p, int v) {    c[p] = a[p] = v;    int lb = lowbit(p);    for (int i = 1; i < lb; i++) {        c[p] = max(c[p], c[pos - i]);    }}void update(int p, int v) {    update_by_child(p, v);    int t = c[p];    for (p = fa(p); p <= N; p = fa(p)) {        if (c[p] > t) {            t = c[p];        } else {            break;        }    }}int query(int l, int r) {    int ret = a[l];    for (; l <= r; ) {        int next = left(r) + 1;        if (next >= l) {            ret = max(ret, c[r]);            r = next - 1;        } else {            ret = max(ret, a[r]);            r--;        }    }    return ret;}

例题解析

hdu[1754] I Hate It

思路：利用树状数组快速代入区间最值。

方法：初始化原数组并通过树状数组维护区间最值，处理每个查询请求或更新操作。

该解决方案在时间复杂度方面保证了效率，特别适用于大规模数据处理场景。

转载地址：http://cdaiz.baihongyu.com/

你可能感兴趣的文章