先附上学习线段树时做的笔记
https://blog.csdn.net/weixin_42172261/article/details/88367758
HDU 1166 敌兵布阵
线段树单点增减
注意update函数中当更新了单点信息后还要pushup
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef struct{
int l, r;
int val, len;
}node;
node tree[50005*4];
int arr[50005];
void pushup(int cur){
tree[cur].val=tree[cur*2].val+tree[cur*2+1].val;
}
void build(int cur, int l, int r){
int mid=(l+r)/2;
tree[cur].l=l, tree[cur].r=r;
tree[cur].val=0;
tree[cur].len=r-l+1;
if (l==r)
tree[cur].val=arr[l];
else{
build(cur*2, l, mid);
build(cur*2+1, mid+1, r);
pushup(cur);
}
}
void update_point(int cur, int pos, int val){
int l=tree[cur].l, r=tree[cur].r;
int mid=(l+r)/2;
if (l==r){
tree[cur].val+=val;
return;
}
if (pos<=mid)
update_point(cur*2, pos, val);
else
update_point(cur*2+1, pos, val);
pushup(cur);
}
int query_interval(int cur, int ql, int qr){
if (ql<=tree[cur].l && tree[cur].r<=qr)
return tree[cur].val;
int ans=0;
int mid=(tree[cur].l+tree[cur].r)/2;
if (ql<=mid)
ans+=query_interval(cur*2, ql, qr);
if (qr>mid)
ans+=query_interval(cur*2+1, ql, qr);
return ans;
}
int main(){
int t, n, cas=0;
scanf("%d", &t);
while (t--){
scanf("%d", &n);
for (int i=1; i<=n; i++)
scanf("%d", &arr[i]);
build(1, 1, n);
printf("Case %d:\n", ++cas);
char s[10];
while (scanf("%s", s)!=EOF){
if (s[0]=='Q'){
int i, j;
scanf("%d%d", &i, &j);
printf("%d\n", query_interval(1, i, j));
}
if (s[0]=='A'){
int i, j;
scanf("%d%d", &i, &j);
update_point(1, i, j);
}
if (s[0]=='S'){
int i, j;
scanf("%d%d", &i, &j);
update_point(1, i, -j);
}
if (s[0]=='E')
break;
}
}
return 0;
}
HDU 1754 I Hate It
单点替换+区间最值
区间最值就是把节点的value改成区间的最值，然后把pushup中的求和改成求最大最小值就可以，其他操作不变。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef struct{
int l, r;
int val, len;
}node;
node tree[200005*4];
int arr[200005];
int n, m;
//注意这里是求max值
void pushup(int cur){
tree[cur].val=max(tree[cur*2].val, tree[cur*2+1].val);
}
void build(int cur, int l, int r){
int mid=(l+r)/2;
tree[cur].l=l, tree[cur].r=r;
tree[cur].val=0, tree[cur].len=r-l+1;
if (l==r)
tree[cur].val=arr[l];
else{
build(cur*2, l, mid);
build(cur*2+1, mid+1, r);
pushup(cur);
}
}
void update(int cur, int pos, int val){
int l=tree[cur].l, r=tree[cur].r;
int mid=(l+r)/2;
if (l==r && l==pos){
tree[cur].val=val;
return;
}
if (pos<=mid)
update(cur*2, pos, val);
else
update(cur*2+1, pos, val);
pushup(cur);
}
int query(int cur, int ql, int qr){
if (ql<=tree[cur].l && qr>=tree[cur].r){
return tree[cur].val;
}
int ans=-1;
int mid=(tree[cur].l+tree[cur].r)/2;
if (ql<=mid)
ans = max(ans, query(cur*2, ql, qr));
if (qr>mid)
ans = max(ans, query(cur*2+1, ql, qr));
return ans;
}
int main(){
while (scanf("%d%d", &n, &m)!=EOF){
for (int i=1; i<=n; i++)
scanf("%d", &arr[i]);
build(1, 1, n);
for (int i=1; i<=m; i++){
char s[5];
int x, y;
scanf("%s%d%d", s, &x, &y);
if (s[0]=='U'){
update(1, x, y);
}else{
printf("%d\n", query(1, x, y));
}
}
}
return 0;
}
HDU 1394 Minimum Inversion Number
单点更新+区间求和
输入的是0到n-1的一个排列，说明没有重复数据，那update的时候就可以把这个数放到其下标的位置。就是0放到下标为0的地方，1放到下标为1的地方，2放到下标为2的地方，以此类推。
最开始建树的时候把val置为0，表示这个l=r的地方还没有数值，在update中有这个值就给赋值为1.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef struct{
int l, r;
int val, len;
}node;
node tree[200005*4];
int arr[200005];
int n;
void pushup(int cur){
tree[cur].val=tree[cur*2].val+tree[cur*2+1].val;
}
void build(int cur, int l, int r){
int mid=(l+r)/2;
tree[cur].l=l, tree[cur].r=r;
tree[cur].val=0, tree[cur].len=r-l+1;
if (l==r){
return;
}else{
build(cur*2, l, mid);
build(cur*2+1, mid+1, r);
}
}
int query(int cur, int l, int r){
if (l<=tree[cur].l && tree[cur].r<=r)
return tree[cur].val;
int res=0;
int mid=(tree[cur].l+tree[cur].r)/2;
if (l<=mid)
res+=query(cur*2, l, r);
if (r>mid)
res+=query(cur*2+1, l, r);
return res;
}
void update(int cur, int pos){
if (tree[cur].l==pos && tree[cur].r==pos){
tree[cur].val=1;
return;
}
int mid=(tree[cur].l+tree[cur].r)/2;
if (pos<=mid)
update(cur*2, pos);
if (pos>mid)
update(cur*2+1, pos);
pushup(cur);
}
int main(){
while (scanf("%d", &n)!=EOF){
int res=0;
build(1, 0, n-1);//区间[0,n-1]
for (int i=1; i<=n; i++){
scanf("%d", &arr[i]);
res += query(1, arr[i], n-1);//从arr[i]到n-1有多少个值为1的
update(1, arr[i]);//将这个值放到线段树叶子节点中
}
//到这里res就是输入排列的逆序数，举个例子模拟一下
int ans=res;
for (int i=1; i<=n; i++){
ans += n-arr[i]-1 -arr[i];//在上一个排列逆序数的基础上，加上比它大的，减去比它小的
res=min(res, ans);
}
printf("%d\n", res);
}
return 0;
}
POJ 3468 A Simple Problem with Integers
线段树区间更新
更新节点分向上更新和向下更新，向上更新就是当一个节点的儿子更新后要更新这个节点
区间更新往往就涉及向下更新，当更新某个区间时还没到叶子节点，如果对于每一个中间的一个节点直接更新到叶子节点会太浪费时间，所以设置一个懒惰标记，这样每次递归时先pushdown一下，再去修改子结点。
代码：https://blog.csdn.net/weixin_42172261/article/details/98478192
