图解线段树

yhlin

发布于 2023-02-27 16:56:19

5800

发布于 2023-02-27 16:56:19

文章被收录于专栏：yhlin's blog

线段树

线段树是算法竞赛中常用的用来维护区间信息的数据结构。线段树可以在 O(\log_{2}{N}) 的时间复杂度内实现单点修改、区间修改、区间查询等操作。

线段树的基本结构

为数组（假设下标从 1 开始）：

a[5] = [{1,2,3,4,5}]

构造线段树如下图（采用堆式存储）：

上述数组 D 用来保存线段树，由于采用的是堆式存储，因此 D[i] 的左右孩子结点分别为 D[2\times i],D[2 \times i + 1]。不难发现上图有两种结点，银色结点括号表示该结点包含的数组 a 的区间，D[i] 的值表示 \sum_{k=i}^{j}a[k]。且若区间两端点相等为 [k,k] 则 D[i] = a[k] 即值为绿色结点。

线段树的建立

由于树树递归定义的，因此其建立也是递归的：

void buildST(int left, int right, int p, vector<int>& D, vector<int> & a)
{if(left == right)
    {D[p] = a[left];
        return;
    }
    int mid = left + (right - left)/2;
    build(left, mid, p*2, D, a);
    build(mid+1, right, p*2+1, D, a);
    D[p] = D[p * 2] + D[p * 2 + 1];
}

线段树的区间查询

区间和：

// [left,right] 为待查区间，[cl,cr] 为当前区间，p 为当前节点编号，D 为线段树的存储数组
int getSum(int left, int right, int cl, int cr, int p, vector<int> &D)
{if(left <= cl && cr <= right) // 当前区间为待查区间的子集
        return D[p];
        // 划分区间，递归查询
    int mid = cl + (cr - cl)/2, sum = 0;
    if(left <= mid) // 与左区间有交集
        sum += getSum(left, right, cl, mid, p * 2, D);
    if(right > mid) // 与右区间有交集
        sum += getSum(left, right, mid+1, cr, p * 2 + 1, D);
    return sum;
}

区间修改：

[cl,cr] 为当前区间，index 为要修改的数组 a 的下标，val 为修改的最终值，p 为当前节点编号。

void updateST(int cl, int cr, int index, int val, int p, vector<int>& D,vector<int>& a)
{if(cl == cr)
    {a[index] = val;
        D[p] = val;
        return;
    }
    else
    {int mid = cl + (cr - cl)/2;
        if(index >= cl && index <= mid)
            updateST(cl, mid, index, val, p * 2, D, a);
        else if(index > mid && index <= cr)
            updateST(mid + 1, cr, index, val, p * 2 + 1, D, a);
        D[p] = D[p * 2] + D[p * 2 + 1];
    }
}

此时如果将 a[1] 改成 6 , 则树变成 (红色表示有修改的节点)：

实验

int main()
{vector<int> D(10,0);
    vector<int> a(6);
    for(int i = 0; i < a.size();i++)
        a[i] = i;

    cout << "Building STree:" << endl;
    buildST(1, 5, 1, D, a);
    cout << "STree:";
    for(int i = 1;i < D.size();i++)
        cout << D[i] << " ";
    cout << endl;
    cout << "================================" << endl;
    cout << "Quary:(1,3)"<< endl;
    cout << getSum(1,3,1,5,1,D) << endl;
    cout << "================================" << endl;
    cout << "Update: a[1] = 6" << endl;
    updateST(1,5,1,6,1,D,a);
    cout << "STree:";
    for(int i = 1;i < D.size();i++)
        cout << D[i] << " ";
    cout << endl;
    cout << "================================" << endl;
    cout << "Quary:(1,3)"<< endl;
    cout << getSum(1,3,1,5,1,D) << endl;

}