有关线段树的一些题目
接近一个星期的学习，蒟蒻总算入门线段树了，贴几类常见线段树题目的代码。如有错误，希望大佬指出。
单点更新求区间和
Sample Input
1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End
Sample Output
Case 1:
6
33
59
AC代码
#include <iostream>
#include <cstring>
using namespace std;
int a[50005];
int c[50005];
inline int lowbit(int k)
{
return k & (-k);
}
inline void update(int k, int x)
{
while (k <= 50005)
{
c[k] += x;
k += lowbit(k);
}
}
inline int getsum(int k)
{
int ans = 0;
while (k > 0)
{
ans += c[k];
k -= lowbit(k);
}
return ans;
}
int main()
{
char s[10];
int t;
scanf("%d", &t);
for (int l = 1; l <= t; l++)
{
memset(c, 0, sizeof c);
int n, q, w;
scanf("%d", &n);
printf("Case %d:\n", l);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
{
for (int j = i - lowbit(i) + 1; j <= i; j++)
c[i] += a[j];
}
while (true)
{
scanf("%s", s);
if (s[0] == 'E')
break;
scanf("%d%d", &q, &w);
if (s[0] == 'A')
update(q, w);
else if (s[0] == 'S')
update(q, -w);
else
printf("%d\n", getsum(w) - getsum(q - 1));
}
}
}
单点更新求区间最大值
Sample Input
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
Sample Output
5
6
5
9
AC代码
#include <iostream>
#include <algorithm>
using namespace std;
struct node
{
int left;//对应数组a
int right;//对应数组a
int maxx;
int mark;//懒惰标记
};
//k对应结构体que
int n, ql, qr, id, val;
int a[200005];
node que[4 * 200005];
//更新最值
void push_up(int k)
{
que[k].maxx = max(que[k << 1].maxx, que[k << 1 | 1].maxx);
}
//传递标记
void push_down(int k)
{
if (que[k].mark != 0)
{
int temp = que[k].mark;
que[k].mark = 0;
que[k << 1].mark += temp;
que[k << 1 | 1].mark += temp;
que[k << 1].maxx += temp;
que[k << 1 | 1].maxx += temp;
}
}
//建树
void build(int left, int right, int k)
{
que[k].left = left;
que[k].right = right;
que[k].mark = 0;
que[k].maxx = 0;
if (left == right)
{
que[k].maxx = a[left];
return;
}
int mid = (left + right) >> 1;
build(left, mid, k << 1);
build(mid + 1, right, k << 1 | 1);
push_up(k);//向上更新最大值
}
//询问最大值
int querymax(int left, int right, int k)
{
if (ql <= left && right <= qr)
return que[k].maxx;
if (right < ql || qr < left)//区间没有交集
return 0;
push_down(k);//向下传递标记
int mid = (left + right) >> 1;
return max(querymax(left, mid, k << 1), querymax(mid + 1, right, k << 1 | 1));
}
void onepoint_update(int left, int right, int k)
{
if (left == right && left == id)
{
que[k].maxx = val;
return;
}
int mid = (left + right) >> 1;
if (id <= mid)
onepoint_update(left, mid, k << 1);
else
onepoint_update(mid + 1, right, k << 1 | 1);
push_up(k);//向上更新最大值
}
void update(int left, int right, int k)
{
if (right < ql || qr < left)
return;
if (ql <= left && right <= qr)
{
que[k].mark += val;
que[k].maxx += val;
return;
}
push_down(k);//向下传递标记
int mid = (left + right) >> 1;
update(left, mid, k << 1);
update(mid + 1, right, k << 1 | 1);
push_up(k);//向上更新最大值
}
int main()
{
int n, m;
char op[2];
while (scanf("%d%d", &n, &m) > 0)
{
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
build(1, n, 1);
while (m--)
{
scanf("%s", op);
if (op[0] == 'Q')
{
scanf("%d%d", &ql, &qr);
printf("%d\n", querymax(1, n, 1));
}
else
{
scanf("%d%d", &id, &val);
onepoint_update(1, n, 1);
}
}
}
}
poj 3468 A Simple Problem with Integers 题目链接
区间更新 区间求和
Sample Input
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
Sample Output
4
55
9
15
AC代码
#include <cstdio>
#include <algorithm>
#define ll long long
struct node
{
int l;
int r;
ll sum;
ll mark;
}que[100005 * 4];
ll val;
int ql, qr;
void push_up(int k)
{
que[k].sum = que[k << 1].sum + que[k << 1 | 1].sum;
}
void push_down(int k)
{
if (que[k].mark)
{
ll temp = que[k].mark;
que[k].mark = 0;
que[k << 1].mark += temp;
que[k << 1 | 1].mark += temp;
que[k << 1].sum += temp * (que[k << 1].r - que[k << 1].l + 1);
que[k << 1 | 1].sum += temp * (que[k << 1 | 1].r - que[k << 1 | 1].l + 1);
}
}
void build(int left, int right, int k)
{
que[k].l = left;
que[k].r = right;
que[k].mark = 0;
if (left == right)
{
scanf("%lld", &que[k].sum);
return;
}
int mid = (left + right) >> 1;
build(left, mid, k << 1);
build(mid + 1, right, k << 1 | 1);
push_up(k);
}
void update(int left, int right, int k)
{
if (right < ql || qr < left)
return;
if (ql <= left && right <= qr)
{
que[k].mark += val;
que[k].sum += val * (que[k].r - que[k].l + 1);
return;
}
push_down(k);
int mid = (left + right) >> 1;
update(left, mid, k << 1);
update(mid + 1, right, k << 1 | 1);
push_up(k);
}
ll querysum(int left, int right, int k)
{
if (right < ql || qr < left)
return 0;
if (ql <= left && right <= qr)
return que[k].sum;
push_down(k);
int mid = (left + right) >> 1;
return querysum(left, mid, k << 1) + querysum(mid + 1, right, k << 1 | 1);
}
int main()
{
int n, m;
char op[2];
scanf("%d%d", &n, &m);
build(1, n, 1);
while (m--)
{
scanf("%s", op);
if (op[0] == 'Q')
{
scanf("%d%d", &ql, &qr);
printf("%lld\n", querysum(1, n, 1));
}
else
{
scanf("%d%d%lld", &ql, &qr, &val);
update(1, n, 1);
}
}
}
区间染色，求最后颜色的数量（这个题目要离散化一下）
Sample Input
1
5
1 4
2 6
8 10
3 4
7 10
Sample Output
4
AC代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
using namespace std;
int ql, qr;
ll val;
int book[200005], a[200005];
struct tttt
{
int a;
int b;
}temp[200005];
struct node
{
int l;
int r;
ll mark;//用来标记这个区间的值，减少更新次数
}que[200005 * 4];
void push_up(int k)
{
;//不用向上更新
}
void push_down(int k)
{
if (que[k].mark)
{
que[k << 1].mark = que[k].mark;
que[k << 1 | 1].mark = que[k].mark;
que[k].mark = 0;
}
}
void build(int left, int right, int k)
{
que[k].l = left;
que[k].r = right;
que[k].mark = 0;
if (left == right)
return;
int mid = (left + right) >> 1;
build(lson);
build(rson);
}
void update(int left, int right, int k)
{
if (ql <= left && right <= qr)
{
que[k].mark = val;
return;
}
if (right < ql || qr < left)
return;
push_down(k);
int mid = (left + right) >> 1;
update(lson);
update(rson);
push_up(k);
}
/* void update(int left, int right, int k) { if (ql <= left && right <= qr) { que[k].mark = val; return; } push_down(k); int mid = (left + right) / 2; if (ql <= mid) update(lson); if (qr > mid) update(rson); } */
void query(int left, int right, int k)
{
if (que[k].mark)
{
book[que[k].mark] = 1;
return;
}
if (left == right)
return;
int mid = (left + right) >> 1;
query(lson);
query(rson);
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int n, tot = 0;
scanf("%d", &n);
memset(book, 0, sizeof book);
for (int i = 0; i < n; i++)
{
scanf("%d%d", &temp[i].a, &temp[i].b);
a[tot++] = temp[i].a;
a[tot++] = temp[i].b;
}
sort(a, a + tot);
for (int i = 0; i < n; i++)
{
temp[i].a = lower_bound(a, a + tot, temp[i].a) - a + 1;
temp[i].b = lower_bound(a, a + tot, temp[i].b) - a + 1;
}
build(1, tot, 1);
for (int i = 0; i < n; i++)
{
ql = temp[i].a;
qr = temp[i].b;
val = i + 1;
update(1, tot, 1);
}
ql = 1; qr = tot;
query(1, tot, 1);
ll ans = 0;
for (int i = 0; i < tot; i++)
if (book[i])
ans++;
printf("%lld\n", ans);
}
}
区间更新为定值，区间求和
Sample Input
1
10
2
1 5 2
5 9 3
Sample Output
Case 1: The total value of the hook is 24.
AC代码
#include <iostream>
#define ll long long
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
using namespace std;
int ql, qr;
ll val;
struct node
{
int l;
int r;
ll sum;
ll mark;
}que[200005 * 4];
void push_up(int k)
{
que[k].sum = que[k << 1].sum + que[k << 1 | 1].sum;
}
void push_down(int k)
{
if (que[k].mark)
{
ll t = que[k].mark;
que[k].mark = 0;
que[k << 1].sum = t * (que[k << 1].r - que[k << 1].l + 1);
que[k << 1 | 1].sum = t * (que[k << 1 | 1].r - que[k << 1 | 1].l + 1);
que[k << 1].mark = t;
que[k << 1 | 1].mark = t;
}
}
void build(int left, int right, int k)
{
que[k].l = left;
que[k].r = right;
que[k].mark = 0;
if (left == right)
{
que[k].sum = 1;
return;
}
int mid = (left + right) >> 1;
build(lson);
build(rson);
push_up(k);
}
void update(int left, int right, int k)
{
if (right < ql || qr < left)
return;
if (ql <= left && right <= qr)
{
que[k].sum = val * (right - left + 1);
que[k].mark = val;
return;
}
push_down(k);
int mid = (left + right) >> 1;
update(lson);
update(rson);
push_up(k);
}
ll querysum(int left, int right, int k)
{
if (right < ql || qr < left)
return 0;
if (ql <= left && right <= qr)
return que[k].sum;
push_down(k);
int mid = (left + right) >> 1;
return querysum(lson) + querysum(rson);
}
int main()
{
int t, l = 1;
scanf("%d", &t);
while (t--)
{
int n, m;
scanf("%d%d", &n, &m);
build(1, n, 1);
while (m--)
{
scanf("%d%d%lld", &ql, &qr, &val);
update(1, n, 1);
}
ql = 1;
qr = n;
printf("Case %d: The total value of the hook is %lld.\n", l++, querysum(1, n, 1));
}
}
区间更新，区间计算数量，加了一点状压思想
Sample Input
2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2
Sample Output
2
1
AC代码
#include <iostream>
#include <algorithm>
#include <cstdio>
int ql, qr, val;
struct node
{
int l;
int r;
int mark;
int sum;
}que[100005 * 4];
void push_up(int k)
{
que[k].sum = que[k << 1].sum | que[k << 1 | 1].sum;
}
void push_down(int k)
{
if (que[k].mark)
{
int t = que[k].mark;
que[k].mark = 0;
que[k << 1].mark = t;
que[k << 1 | 1].mark = t;
que[k << 1].sum = t;
que[k << 1 | 1].sum = t;
}
}
void build(int left, int right, int k)
{
que[k].l = left;
que[k].r = right;
que[k].mark = 0;
if (left == right)
{
que[k].sum = 1;
return;
}
int mid = (left + right) >> 1;
build(left, mid, k << 1);
build(mid + 1, right, k << 1 | 1);
push_up(k);
}
void update(int left, int right, int k)
{
if (right < ql || qr < left)
return;
if (ql <= left && right <= qr)
{
que[k].mark = 1 << (val - 1);
que[k].sum = 1 << (val - 1);
return;
}
push_down(k);
int mid = (left + right) >> 1;
update(left, mid, k << 1);
update(mid + 1, right, k << 1 | 1);
push_up(k);
}
int query(int left, int right, int k)
{
if (right < ql || qr < left)
return 0;
if (ql <= left && right <= qr)
return que[k].sum;
push_down(k);
int mid = (left + right) >> 1;
return query(left, mid, k << 1) | query(mid + 1, right, k << 1 | 1);
}
int main()
{
int n, q;
char op[2];
while (scanf("%d%*d%d", &n, &q) > 0)
{
build(1, n, 1);
while (q--)
{
scanf("%s", op);
if (op[0] == 'C')
{
scanf("%d%d%d", &ql, &qr, &val);
update(1, n, 1);
}
else
{
scanf("%d%d", &ql, &qr);
if (ql > qr)
{
ql ^= qr;
qr ^= ql;
ql ^= qr;
}
int ans = query(1, n, 1);
int cnt = 0;
while (ans)
{
if (ans & 1)
cnt++;
ans >>= 1;
}
printf("%d\n", cnt);
}
}
}
}
查看16道真题和解析