线段树模板,支持对区间做运算并求sum,基于POJ 3468
需要注意:

  • 数组开4倍大
  • 因为区间操作较频繁故打标记
  • 注意Update操作的位置
  • 均为1~n,所以包括左右,分段递归注意端点要被包含
#define MAXN 1000010
int arr[MAXN];
struct Node
{
    int l, r;
    int add, value;
}tree[MAXN * 4];
int sum = 0;
void Update(int id)
{
    if (tree[id].add)
    {
        tree[id << 1].add += tree[id].add;
        tree[(id << 1) + 1].add += tree[id].add;
        tree[id << 1].value += tree[id].add * (tree[id << 1].r - tree[id << 1].l + 1);
        tree[(id << 1) + 1].add += tree[id].add;
        tree[(id << 1) + 1].value += tree[id].add * (tree[(id << 1) + 1].r - tree[(id << 1) + 1].l + 1);
        tree[id].add = 0;
    }
}
void Build(int id, int l, int r)
{
    tree[id].l = l;
    tree[id].r = r;
    if (l == r)
    {
        tree[id].value = arr[l];
        return;
    }
    int mid = (l + r) >> 1;
    Build(id << 1, l, mid);
    Build((id << 1) + 1, mid + 1, r);
    tree[id].value = tree[id << 1].value + tree[(id << 1) + 1].value;
}
void Add(int id, int l, int r, int v)
{
    if (l <= tree[id].l && tree[id].r <= r)
    {
        tree[id].add += v;
        tree[id].value += v * (tree[id].r - tree[id].l + 1);
        return;
    }
    Update(id);
    if (tree[id].l == tree[id].l)
        return;
    int mid = (tree[id].l + tree[id].r) >> 1;
    if (l > mid)
        Add((id << 1) + 1, l, r, v);
    else if (r <= mid)
        Add(id << 1, l, r, v);
    else
    {
        Add(id << 1, l, mid, v);
        Add((id << 1) + 1, mid + 1, r, v);
    }
    tree[id].value = tree[id << 1].value + tree[(id << 1) + 1].value;
}
void Solve(int id, int l, int r)
{
    if (l <= tree[id].l && tree[id].r <= r)
    {
        sum += tree[id].value;
        return;
    }
    Update(id);
    if (tree[id].l == tree[id].r)
        return;
    int mid = (tree[id].l + tree[id].r) >> 1;
    if (l > mid)
        Solve((id << 1) + 1, mid + 1, r);
    else if (r <= mid)
        Solve(id << 1, l, mid);
    else
    {
        Solve(id << 1, l, mid);
        Solve((id << 1) + 1, mid + 1, r);
    }
}