关于树状数组和线段树的模板

树状数组的作用：

        1、快速求前缀和。

        2、将某个值进行改变。

三个函数。

int o[N];
int lowbit(int x)
{
    return x & -x;
}
int query(int x) //查询从开始到第x个数的和。
{
    int s = 0;
    for(int i = x; i; i -= lowbit(i)) s += o[i];
    return s;
}
void add(int x, int y)//将第x个数加上y。
{
    for(int i = x; i <= n; i += lowbit(i)) o[i] += y;
}

线段树

  线段树在建树的时候节点数应该为四倍长度。

const int N = 1e5 + 10;
typedef struct 
{
    int l, r;
    int sum;
}aa;
aa o[N * 4];// 四倍长度
int p[N];//初始数组
int n, m;

void pushup(int u) //向上更新
{
    o[u].sum = o[u << 1].sum + o[u << 1 | 1].sum;
}
void bulid(int k, int l, int r)//建树
{
    if(l == r) //
        o[k] = {l, r, p[l]};
    else
    {
        int mid = l + r >> 1;
        o[k] = {l, r, 0};
        bulid(k << 1, l, mid);
        bulid(k << 1 | 1, mid + 1, r);
        pushup(k);
    }
}

int query(int k, int l, int r)
{
    if(l <= o[k].l && o[k].r <= r) return o[k].sum;
    
    int mid = o[k].r + o[k].l >> 1;
    int s = 0;
    if(l <= mid) s += query(k << 1, l, r);
    if(mid < r) s += query(k << 1 | 1, l, r);
    return s;
}
void modify(int k, int a, int b)
{
    if(o[k].r == o[k].l) o[k].sum += b;
    else
    {
        int mid = o[k].r + o[k].l >> 1;
        if(a <= mid) modify(k << 1, a, b);
        else modify(k << 1 | 1, a, b);
        pushup(k);
    }
}