经典线段树
<pre><code class="language-cpp">#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);
}</code></pre>