线段树的单点查询
- 先判断当前区间[ l , r ] [l,r][l,r]是否与目标区间完全相等
inline int query(int pos, int L, int l, int r)
{
if (L == l && r == L)
{
return tree[pos];
}
int mid = (l + r) >> 1;
int sum = 0;
push_down(pos, l, r);
if (L <= mid)
{
sum += query(lw, L, l, mid);
}
else
{
sum += query(rw, L, mid + 1, r);
}
push_up(pos);
return sum;
}
- 下发标记,请参考
就是玩儿 - 分解区间
- 上传标记
线段树的区间修改
模板
#include <bits/stdc++.h>
using namespace std;
#define lw pos << 1
#define rw pos << 1 | 1
#define int long long
const int maxn = 1e6 + 5;
int n, m;
int tree[maxn << 2], lazy[maxn << 2];
inline void push_up(int pos)
{
tree[pos] = tree[lw] + tree[rw];
}
inline void js(int pos, int l, int r, int k)
{
lazy[pos] += k;
tree[pos] += k * (r - l + 1);
}
inline void push_down(int pos, int l, int r)
{
int mid = (l + r) >> 1;
js(lw, l, mid, lazy[pos]);
js(rw, mid + 1, r, lazy[pos]);
lazy[pos] = 0;
}
inline void build(int pos, int l, int r)
{
lazy[pos] = 0;
if (l == r)
{
cin >> tree[pos];
return;
}
int mid = (l + r) >> 1;
build(lw, l, mid);
build(rw, mid + 1, r);
push_up(pos);
}
inline void update(int pos, int left, int right, int l, int r, int val)
{
if (left <= l && r <= right)
{
lazy[pos] += val;
tree[pos] += val * (r - l + 1);
return;
}
push_down(pos, l, r);
int mid = (l + r) >> 1;
if (left <= mid)
update(lw, left, right, l, mid, val);
if (right > mid)
update(rw, left, right, mid + 1, r, val);
push_up(pos);
}
inline int query(int pos, int L, int l, int r)
{
if (L == l && r == L)
{
return tree[pos];
}
int mid = (l + r) >> 1;
int sum = 0;
push_down(pos, l, r);
if (L <= mid)
{
sum += query(lw, L, l, mid);
}
else
{
sum += query(rw, L, mid + 1, r);
}
push_up(pos);
return sum;
}
signed main()
{
cin >> n >> m;
build(1, 1, n);
for (int i = 1, q, q1, q2, q3; i <= m; i++)
{
cin >> q >> q1;
if (q == 1)
{
cin >> q2 >> q3;
update(1, q1, q2, 1, n, q3);
}
else if (q == 2)
{
cout << query(1, q1, 1, n) << endl;
}
}
return 0;
}
版权声明:本文为qq_46258139原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。