线段树学习笔记

学习链接

代码（未完成）

#include<bits/std++.h>
using namespace std;

int array[200005],tree[200005<<2]; // array是初始数组，tree是线段树
void update(int item) // 更新 item 号节点的函数，这里是最大值，也可更改为区间和、最小值等
{
    tree[item]=max(tree[item<<1],tree[item<<1|1]); // item<<1 是左子树下标，item<<1|1 是右子树下标
}

void build_tree(int item,int left,int right) // item 表示要建立的节点编号，left 和 right 表示需要建立区间的左、右端点
{
    if(left==right) // 这是一个叶子结点
    {
        tree[item]=left; // 直接赋值
        return;
    }

    int mid=(left+right)/2; // 把区间分成两半
    build_tree(item<<1,left,mid); // 建立左子树
    build_tree(item<<1|1,mid+1,right); // 建立右子树
    update(item); // 更新自己
}

void change(int changeItem,int val,int left,int right,int nowItem)
{
    if(left==right) // 叶子结点
    {
        array[nowItem]=val;
        tree[nowItem]=val; // 线段树和原数组都要更新
    }
    int mid=(left+right)/2; // 把区间分成两半
    if(changeItem<mid) // 需要更新的结点在左子树
    {
        change(changeItem,val,left,mid,k<<1);
    }
    else // 在右子树
    {
        change(changeItem,val,mid+1,right,k<<1|1);
    }
    update(nowItem); // 更新自己
}

int main(void)
{

}