【算法】【线段树】关于线段树是否必须开4N的问题

问题描述：

使用线段树的时候，我们通常会开一个4N的数组，而不是2N，这是为什么呢？

问题分析：

线段树一般是二叉树，所以我们可以用数组来表示，而且数组的大小是 \(2^k\) ，这样就可以用位运算来表示左右子树了。按照完全二叉树判断，所需节点数为 \(2^{k+1}-1\)，其中\(k\)为树的层数。如果我们存入的数据恰好为\(2^k\)个，显然我们只需要开2N个节点。那么我们为什么开4N个节点甚至更多？

完全二叉树

当考虑一般平衡二叉树时：

由于我们分割线段直接从中间分开，导致左右子树所包含的节点数不一定为\(2^k\)，所以左右子树都可能是一般的平衡二叉树，导致中间多出空白节点。

红线为需要占用空间的未使用节点

解决问题的思路很简单，只需要我们在分割一段长为 \(N\) 的线段时，一直保证右子树为 \(\displaystyle2 ^k \leq \frac{N}{2}\) 个叶子节点（形成完全二叉树），左子树则为 \(N-2^k\) 个叶子节点（形成平衡二叉树）。

更换分割方式后形成的平衡二叉树

这样二叉树数组只需要开 \(2N-1\) 即可。通常第0个节点空出，则只需开 \(2N\) 。

当然这样建树时需要计算线段分割点，耗时稍久，其他代码相同（如果节点没有保存区间左右端点，则查询和更新时遇到每个节点都需要计算一次分割点，比较耗时）。

分割点计算方式如下：

// 获取数字二进制位数，复杂度为O(n)
// 也可通过二分查表法实现O(log(n))的复杂度
int getBinaryDigit(int num) {
    int digit = 0;
    while (num) {
        num >>= 1;
        digit++;
    }
    return digit;
}
// 获取线段树中点，复杂度为O(n), n为数字位数
int getSegPoint(int l, int r) {
    int digit = getBinaryDigit((r - l + 1) >> 1);
    return (digit == 0 ? r : r - (1 << (digit - 1)));
}

完整的代码如下：

#include <bits/stdc++.h>
using namespace std;
// 获取数字二进制位数，复杂度为O(n)
// 也可通过二分查表法实现O(log(n))的复杂度
int getBinaryDigit(int num) {
    int digit = 0;
    while (num) {
        num >>= 1;
        digit++;
    }
    return digit;
}
// 获取线段树中点，复杂度为O(n), n为数字位数
int getSegPoint(int l, int r) {
    int digit = getBinaryDigit((r - l + 1) >> 1);
    return (digit == 0 ? r : r - (1 << (digit - 1)));
}
// 线段树节点，r,l为区间，v为区间和，lazy为懒标记（表示子节点需要加上的值）
struct Node {
    int r, l, lazy;
    long long v;
};
// 线段树
template <int Tr_N>
struct SegTree {
// Tr_N为线段树数组大小，必须大于等于区间长度
// #define Tr_N 10
#define ld (d << 1)      // 2d       左子节点
#define rd (d << 1 | 1)  // 2d+1     右子节点
#define TreeSize (Tr_N << 1)
    // tr为线段树数组，取2.7倍防止数组越界，也可以开4倍
    Node tr[TreeSize];
    // 合并子节点信息（这里是区间和，所以是加法）
    inline void push(int d) {
        tr[d].v = tr[ld].v + tr[rd].v;
    }
    // 建树，d为当前节点，l,r为区间
    // 调用时禁止传入参数d
    inline void build(int l, int r, int d = 1) {
        tr[d].l = l;
        tr[d].r = r;
        tr[d].lazy = 0;
        if (l == r) {
            cin >> tr[d].v;  // 输入叶节点值
            // tr[d].v = 0;  // 若无初始值输入，请直接赋值
            return;
        }
        int MID = getSegPoint(l, r);
        build(l, MID, ld);
        build(MID + 1, r, rd);
        push(d);
    }
    // 下发lazy标记，更新子节点的值与lazy标记
    // （注：有lazy标记的节点的值已经被更新过了，它的子节点的值还没有被更新）
    inline void lazydown(int d) {
        if (tr[d].lazy) {
            // 注意这里的区间长度，是子节点的区间长度
            tr[ld].v += tr[d].lazy * (tr[ld].r - tr[ld].l + 1);  
            
            tr[rd].v += tr[d].lazy * (tr[rd].r - tr[rd].l + 1);  
            tr[ld].lazy += tr[d].lazy;
            tr[rd].lazy += tr[d].lazy;
            tr[d].lazy = 0;
        }
    }
    // 区间更新，[x,y]为区间，lazy为增量, d为当前节点
    inline void update(int x, int y, int lazy, int d = 1) {
        if (x <= tr[d].l && y >= tr[d].r) {
            tr[d].v += lazy * (tr[d].r - tr[d].l + 1);
            tr[d].lazy += lazy;
            return;
        }
        lazydown(d);
        // int MID = ((tr[d].l+tr[d].r)>>1);
        int MID = tr[ld].r;
        if (x <= MID)
            update(x, y, lazy, ld);
        if (y > MID)
            update(x, y, lazy, rd);
        push(d);
    }
    // 单点更新，x为更新点，lazy为增量, d为当前节点（内部使用无需传参）
    inline void point_update(int x, int lazy, int d = 1) {
        if (tr[d].l == tr[d].r) {
            tr[d].v += lazy;
            return;
        }
        lazydown(d);
        // int MID = ((tr[d].l + tr[d].r) >> 1);
        int MID = tr[ld].r;
        if (x <= MID)
            point_update(x, lazy, ld);
        else
            point_update(x, lazy, rd);
        push(d);
    }
    // 区间查询，[x,y]为查询区间，d为当前节点
    inline long long query(int x, int y, int d = 1) {
        if (x <= tr[d].l && y >= tr[d].r)
            return tr[d].v;
        lazydown(d);  // 先更新子节点再查询子节点
        // int MID = ((tr[d].l+tr[d].r)>>1);
        int MID = tr[ld].r;
        if (x <= MID) {
            if (y > MID)
                return query(x, y, ld) + query(x, y, rd);
            return query(x, y, ld);
        }
        if (y > MID)
            return query(x, y, rd);
        return 0;
    }
    // 单点查询，x为查询点，d为当前节点（内部使用无需传参）
    inline long long point_query(int x, int d = 1) {
        if (tr[d].l == tr[d].r)
            return tr[d].v;
        lazydown(d);  // 先更新子节点再查询子节点
        // int MID = ((tr[d].l + tr[d].r) >> 1);
        int MID = tr[ld].r;
        if (x <= MID)
            return point_query(x, ld);
        else
            return point_query(x, rd);
    }
    // 打印区间值，[x,y]为区间，update_lazy为是否更新lazy标记
    // 若不更新lazy标记，则打印的是原始值没有更新过的值
    inline void printValue(int x, int y, bool update_lazy = true) {
        if (update_lazy) {
            for (int i = x; i <= y; i++) {
                cout << point_query(i) << " ";
            }
            cout << endl;
        }
        else {
            int digit = getBinaryDigit(y - x + 1);
            int baseNum = 1 << (digit - 1);
            int outNum = (y - x + 1) - baseNum;
            for (int d = baseNum; d < 2 * baseNum; d++) {
                if (tr[d].l == tr[d].r)
                    cout << tr[d].v << " ";
                else {
                    cout << tr[ld].v << " " << tr[rd].v << " ";
                }
            }
            cout << endl;
        }
    }
    // 打印线段树，num_digit为每个节点的数字十进制位数，用于对齐
    inline void printTree(int num_digit = 3) {
        int tree_layer = getBinaryDigit(Tr_N);
        if ((1 << (tree_layer - 1)) < Tr_N)
            tree_layer++;   // 若线段树数组大小不是2的幂次方，则需要增加一层
        int space = (num_digit + 1) * ((1 << (tree_layer - 1)) - 1) + 1;
        int delta = (num_digit + 1) * (1 << (tree_layer - 2));

        int node_num = 1, pre = 1, flag = 0;
        for (int i = 1; i < TreeSize; i++) {
            if (flag)   // 打印区间
                cout << string(space, ' ') << std::right << setw(num_digit) 
                     << setfill(' ') << tr[i].v << "|"
                     << std::left << setw(num_digit) << setfill(' ') 
                     << tr[i].lazy << string(space - 1, ' ');
            else        // 打印值和lazy标记
                cout << string(space, ' ') << '[' << std::right 
                     << setw(num_digit - 1) << setfill(' ') << tr[i].l 
                     << "," << std::left << setw(num_digit - 1) 
                     << setfill(' ') << tr[i].r << ']' << string(space - 1, ' ');
            if (i + 1 == TreeSize) {
                if (flag) {
                    cout << endl;
                    break;
                }
                else {
                    i = pre - 1;
                    cout << endl;
                    flag = 1;
                }
            }
            if (i == node_num * 2 - 1) {
                if (flag) {
                    cout << endl;
                    space -= delta;
                    delta /= 2;
                    node_num *= 2;
                    flag = 0;
                    pre = i + 1;
                }
                else {
                    i = pre - 1;
                    cout << endl;
                    flag = 1;
                }
            }
        }
        cout << endl;
    }
// #undef Tr_N
#undef ld
#undef rd
#undef TreeSize
};
int main() {
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    SegTree<10> segtree;
    int m, n;
    cin >> n >> m;
    // n为数组长度，m为操作数，请自行修改
    // 请注意修改Tr_N的大小，Tr_N为线段树数组大小，必须大于等于n
    // 若无初始值，请修改build中输入叶节点的cin代码
    segtree.build(1, n);
    int op, x, y;
    long long k;
    int num_digit = 3;
    while (m--) {
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> k;
            segtree.update(x, y, k);
        }
        else if (op == 2) {
            cin >> x >> y;
            cout << segtree.query(x, y) << '\n';
        }
        else if (op == 3) {
            segtree.printValue(1, n);
        }
        else if (op == 4) {
            segtree.printTree(num_digit);
        }
        else if (op == 5) {
            cin >> x >> k;
            segtree.point_update(x, k);
        }
        else if (op == 6) {
            cin >> num_digit;
        }
    }
    return 0;
}

输入如下：

10 100 1 2 3 4 5 6 7 8 9 10
4
1 1 5 7
4

输出：

输出

注：每个节点的信息为：

​ [ left, right ]

​ value | lazy_tag

可以清楚地看到改变分割方式后的线段树。开 \(2N\) 没有问题。