[C++基础算法]线段树的简单理解和基本 *** 作讲解 - 1

[C++基础算法]线段树的简单理解和基本 *** 作讲解 - 1

我们知道数组中点的更新的时间复杂度为O(1)，区间求和时间复杂度为O(n)，当数组非常大时，且 *** 作非常多时，这个复杂度是非常可怕的。使用“线段树”可以使更新和查询的时间复杂度都变为O(logN)，可以降低整体的时间复杂度。

本文会讲解线段树的建立，查询 *** 作。（毕竟是简单理解嘛）

其他 *** 作如点更新，区间更新，lazytag将在以后的文章中讲解。

先用一道题来引入今天的重点数据结构，线段树。

洛谷P3353 - 在你窗外闪耀的星星

分析一下这道题，主要 *** 作涉及区间的求和与查询，不存在区间或者点的更新，所以用前缀和可以做，如果涉及更新的话，可以试试差分数组（但是容易TLE）。

接下来的简单 *** 作将依据这道题展开。

如何创建线段树

线段树是一颗二叉树，所以我们可以使用创建二叉树的方法来创建一颗线段树，一般采用数组对树进行模拟，下图为线段树的大致形状（数字表示节点标识，暂时不要管线段树的值的含义）。

我们把1定义为根（2,3为1的两个儿子,1为2,3的父亲），不难发现，二叉树节点中第n个节点的两个子节点分别为 2 * n 和 2 * n + 1，我们通过这个关系来建立树。

可能有同学会疑惑节点10和11在哪里，其实节点10和11是5的左儿子和右儿子，但是5没有儿子，所以舍弃了这两个，这是二叉树的内容，不展开讲解。

我们创建一个数组来存放星星的位置和亮度，显然用数组。（注意一个位置可能有多个星星，亮度需要叠加），创建一个四倍maxn大小的数组来存放线段树，

typedef long long LL;
const int maxn = 1e5 + 10;
int n = 0;//控制边界，由数据决定
LL star[maxn],tree[maxn << 2];//maxn << 2 等价于 maxn * 4（位运算基础）

接下来写一个build_tree()函数，来“递归的”建立线段树，本题建立的是最基础的“区间和线段树”，每个节点表示一段区间的和。

每个节点有三个属性：

• 节点标识
• 区间范围（可以计算出来，无需保存）
• 区间和

void pushup(int node)//辅助收拢函数
{
    tree[node] = tree[node << 1] + tree[node << 1 | 1];//当前节点为两个子节点之和
}

void build_tree(int node = 1,int l = 1,int r = n)//[l,r]为节点表示的区间
{
    //递归出口
    if(l == r)//当节点范围为一个点时
    {
        tree[node] = star[l];//节点值等于该点值，star[r]也可
        return;//递归中断
    }
    //递归主体
    int mid = l - ((r - l) >> 1);//计算当前区间中间值，用于递归往下寻找
    build_tree(node << 1,l,mid);//获取两个儿子的值
    build_tree(node << 1|1,mid + 1,r);//node << 1 | 1相当于node * 2 + 1
    //将两个儿子的值收拢到该节点中
    pushup(node);
    return;
}

没错就是这么简单，当star数组输入完毕后，直接调用build_tree()函数即可建立tree数组，无需传入参数。

假设star数组为下图所示，线段树将会长这样。

 原谅我丑陋的图画。不难发现，图中的叶子节点（没有子节点的最末尾的节点）都是一个大小为1的区间，即单个点。每个节点的值为sum = 两个子节点的sum之和。

如何查询区间和

我们写一个query函数，用于查询[L,R]的区间和，原理是一旦找到完全包含于[L,R]的节点就直接返回该节点的值，这样多个小区间相加，一定可以得到整个[L,R]的和。

比如我想找区间[2,6]，就可以返回 sum[2,2] + sum[3,4] + sum[5,6] ，也就是节点 9 5 6的和，在区间较小时看不出优势，当区间和整个树较大时效率提升很大。

LL query(int L,int R,int node = 1,int l = 1,int r = n)
{
    //先写递归出口，防止死循环
    if(r < L || R < l)return 0;//若不是完全包含则返回0
    else if(L <= l && r <= R)return tree[node];//若完全包含于[L,R]则为符合要求的线段，需要返回累加
    //递归主体
    int mid = l + ((r - l) >> 1);//定义中点
    LL sum1 = query(L,R,node << 1,l,mid);//往下查找左儿子中符合要求的线段和
    LL sum2 = query(L,R,node<<1|1,mid+1,r);//找右边
    return sum1 + sum2;//返回和
}

能够建立线段树和查询区间和就可以解决这道题了。

完整AC代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 10;
int n = 0;//控制边界，由数据决定
LL star[maxn],tree[maxn << 2];//maxn << 2 等价于 maxn * 4（位运算基础）

void pushup(int node)//辅助收拢函数
{
    tree[node] = tree[node << 1] + tree[node << 1 | 1];//当前节点为两个子节点之和
}

void build_tree(int node = 1,int l = 1,int r = n)//[l,r]为节点表示的区间
{
    //递归出口
    if(l == r)//当节点范围为一个点时
    {
        tree[node] = star[l];//节点值等于该点值，star[r]也可
        return;//递归中断
    }
    //递归主体
    int mid = l + ((r - l) >> 1);//计算当前区间中间值，用于递归往下寻找
    build_tree(node << 1,l,mid);//获取两个儿子的值
    build_tree(node << 1|1,mid + 1,r);//node << 1 | 1相当于node * 2 + 1
    //将两个儿子的值收拢到该节点中
    pushup(node);
    return;
}

LL query(int L,int R,int node = 1,int l = 1,int r = n)
{
    //先写递归出口，防止死循环
    if(r < L || R < l)return 0;//若不是完全包含则返回0
    else if(L <= l && r <= R)return tree[node];//若完全包含于[L,R]则为符合要求的线段，需要返回累加
    //递归主体
    int mid = l + ((r - l) >> 1);//定义中点
    LL sum1 = query(L,R,node << 1,l,mid);//往下查找左儿子中符合要求的线段和
    LL sum2 = query(L,R,node<<1|1,mid+1,r);//找右边
    return sum1 + sum2;//返回和
}


int main()
{
    //freopen("in.txt","r",stdin);
    int N,W;
    scanf("%d %d",&N,&W);
    while(N --)
    {
        int X;
        LL B;
        scanf("%d %d",&X,&B);
        star[X] += B;//可能存在多个星星在同一位置
        n = max(n,X);//获取边界
    }//读入完毕
    build_tree();
    LL ans = 0;
    for(int i = 0; i <= n - W + 1; ++i)
    {
        LL sum = query(i, i + W - 1);
        ans = max(ans,sum);
    }
    cout << ans << endl;
    return 0;
}