经典线段树

#include <iostream>
using namespace std;
typedef long long ll;
const ll maxn = 1e6+5;
struct Node{
    int l;
    int r;
    ll addlazy;
    ll sum;
};
Node tree[maxn<<2];
void pushdown(int now){
    tree[2*now].addlazy += tree[now].addlazy;
    tree[2*now+1].addlazy += tree[now].addlazy;
    tree[2*now].sum += tree[now].addlazy * (tree[2*now].r - tree[2*now].l + 1);
    tree[2*now+1].sum += tree[now].addlazy * (tree[2*now+1].r - tree[2*now+1].l + 1);
    tree[now].addlazy = 0;
    return;
}
void build(Node *tree, int now, int l, int r){
    tree[now].l = l;
    tree[now].r = r;
    tree[now].addlazy = 0;
    if(l == r){
        cin >> tree[now].sum;
        return;
    }
    int mid = (l + r) >> 1;
    build(tree, 2*now, l, mid);
    build(tree, 2*now+1, mid+1, r);
    tree[now].sum = tree[2*now].sum + tree[2*now+1].sum;
    return;
}
void updata(Node *tree, int now, int z, ll data){
    if(tree[now].l == tree[now].r){
        tree[now].sum = data;
        return;
    }
    if(tree[now].addlazy)    pushdown(now);
    int mid = (tree[now].l + tree[now].r) >> 1;
    if(z <= mid)    updata(tree, 2*now, z, data);
    else    updata(tree, 2*now+1, z, data);
    tree[now].sum = tree[2*now].sum + tree[2*now+1].sum;
    return;
}
ll ask(Node *tree, int now, int z){
    if(tree[now].l == tree[now].r){
        return tree[now].sum;
    }
    if(tree[now].addlazy)    pushdown(now);
    int mid = (tree[now].l + tree[now].r) >> 1;
    if(z <= mid)    return ask(tree, 2*now, z);
    else    return ask(tree, 2*now+1, z);
}
void upgrade(Node *tree, int now, int l, int r, ll data){
    if(tree[now].l >= l && tree[now].r <= r){
        tree[now].sum += data * (tree[now].r - tree[now].l + 1);
        tree[now].addlazy += data;
        return;
    }
    if(tree[now].addlazy)    pushdown(now);
    int mid = (tree[now].l + tree[now].r) >> 1;
    if(l <= mid)    upgrade(tree, 2*now, l, r, data);
    if(r > mid)    upgrade(tree, 2*now+1, l, r, data);
    tree[now].sum = tree[2*now].sum + tree[2*now+1].sum;
    return;
}
ll query(Node *tree, int now, int l, int r){
    if(tree[now].l >= l && tree[now].r <= r)    return tree[now].sum;
    if(tree[now].addlazy)    pushdown(now);
    int mid = (tree[now].l + tree[now].r) >> 1;
    return (l <= mid? query(tree, 2*now, l, r): 0) + (r > mid? query(tree, 2*now+1, l, r): 0);
}