线段树（C++）

线段树的本质就是树状数组，只不过线段树不再需要lowbit函数来定位对应数据的存储位置，取而代之的则是直接计算分叉结果位置。

node结构体

​ 通常而言，线段树所需要的存储空间约等于原数组的4倍。由于线段树需要存储区间的范围，所以我们需要自己定义一个新结构体来方便存储：

const int N = [题目数据上限];
struct node{
    int l, r;//当前节点的左右区间
    int sum;//当前节点的总和，这部分可以依据题目进行改变
}
node t[N*4];

build函数

​ 有了数据，那就得建树，也就是build函数的意义。build函数在建树过程中，会以递归的形式不停的访问左右区间，直到区间的大小为1，也就是抵达了数据最本身，这时候便可以开始往回传递值，层层传递回去，完成建树。

例如：

build函数结束时：        10
递归的上一层：          3   7
原始数据（递归的底层）：1 2 3 4

那么在数组里，他看起来究竟是什么样的，这里有一份输出可以参考着理解：

数据：1 2 3 4
at node[1]={l:1, r:4, sum:10}     
at node[2]={l:1, r:2, sum:3}      
at node[3]={l:3, r:4, sum:7}      
at node[4]={l:1, r:1, sum:1}      
at node[5]={l:2, r:2, sum:2}      
at node[6]={l:3, r:3, sum:3}      
at node[7]={l:4, r:4, sum:4}  

这样看起来就方便理解许多了。

build函数代码如下：

void build(int u, int l, int r)
{
    if(l == r)
        t[u] = {l, r, w[r]};
    else
    {
        t[u] = {l,r};
        int mid = (l+r) >> 1;
        build(u<<1, l, mid);
        build(u<<1|1, mid+1, r);
        pushup(u);
    }
}

代码中的u<<1以及u<<1|1实际上对应的操作等同于u*2和u*2+1，位运算能优化一些比较常数级的东西，有时候也还是不得不相信常数级玄学的，说不准优化个常数就AC了呢。

pushup函数

​ 将左右分支的结果汇总到上层分支（也就是函数传参的u）

void pushup(int u){
    t[u].sum = t[u<<1].sum + t[u<<1|1].sum;
}

query函数

​ 查询区间的结果。查询需要从根节点开始一层一层向下查询，所以第一次调用的时候需要从u=1开始。查询过程为：如果当前区间已经满足了查询要求（也就是说当前的区间已经包含查询范围内，不需要完全等于），则可以返回sum值。如果当前区间范围太大，则分别向左半边区间和右半边区间查询，直到拿到查询区间内的所有信息。

int query(int u, int l, int r)
{
    if(t[u].l >= l && t[u].r <= r)
        return t[u].sum;
    int mid = (t[u].l + t[u].r) >> 1;
    int sum = 0;
    if(l<=mid)
        sum += query(u<<1, l, r);
    if(r > mid)
        sum += query(u<<1|1, l, r);
    return sum;
}

modify函数

​ 修改区间。仍然还是一样从根节点u=1开始向下遍历，这回我们需要找到对应数字，再进行修改，修改完成后再次进行pushup。

void modify(int u, int x, int v)
{
    if(t[u].l == t[u].r)
        t[u].sum += v;
    else
    {
        int mid = t[u].l + t[u].r >> 1;
        if(x <= mid)
            modify(u<<1, x, v);
        else
            modify(u<<1|1, x, v);
        pushup(u);
    }
}

汇总以上代码便可得到另一个class：

class SegmentTree
{
private:
    struct node{
        int l,r;
        int sum;
    };
    int size;
    static const int N=100010;
    node t[N*4];
    int w[N];


public:
    void getArray(vector<int> nu)
    {
        for(int i : nu)
        {
            size++;
            w[size] = i;
        }
        build(1, 1, size);
    }
    void build(int u, int l, int r)
    {
        if(l == r)
            t[u] = {l, r, w[r]};
        else
        {
            t[u] = {l,r};
            int mid = (l+r) >> 1;
            build(u<<1, l, mid);
            build(u<<1|1, mid+1, r);
            pushup(u);
        }
    }
    void pushup(int u)
    {
        t[u].sum = t[u<<1].sum + t[u<<1|1].sum;
    }
    int query(int u, int l, int r)
    {
        if(t[u].l >= l && t[u].r <= r)
            return t[u].sum;
        int mid = (t[u].l + t[u].r) >> 1;
        int sum = 0;
        if(l<=mid)
            sum += query(u<<1, l, r);
        if(r > mid)
            sum += query(u<<1|1, l, r);
        return sum;
    }
    void modify(int u, int x, int v)
    {
        if(t[u].l == t[u].r)
            t[u].sum += v;
        else
        {
            int mid = t[u].l + t[u].r >> 1;
            if(x <= mid)
                modify(u<<1, x, v);
            else
                modify(u<<1|1, x, v);
            pushup(u);
        }
    }
};

树状数组和线段树的Snippet会在下一篇中放出。