1. 首页
2. 线段树
3. 本页

线段树单点更新(一)

单点更新:最最基础的线段树,只更新叶子节点,然后把信息用 PushUP(int r)这个函数更新上来。

hdu1166 敌兵布阵

线段树功能:update:单点增减 query:区间求和

#include <bits/stdc++.h>
using namespace std;

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

const int MAXN = 50550;

int sum[MAXN << 2];

void pushup(int rt)
{
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

void build(int l, int r, int rt)
{
	if (l == r) {
		scanf("%d",&sum[rt]);
		return;
	}
	int m=(l+r)>>1;
	build(lson);
	build(rson);
	pushup(rt);
}

void update(int pos,int res,int l,int r,int rt)
{
	if(l==r)
	{
		sum[rt]+=res;
		return;
	}
	int m=(l+r)>>1;
	if(pos<=m)
	{
		update(pos,res,lson);
	}
	else
	{
		update(pos,res,rson);
	}
	pushup(rt);
}

int query(int ql,int qr,int l,int r,int rt)
{
	if(ql<=l && r<=qr)
	{
		return sum[rt];
	}
	int res=0;
	int m=(l+r)>>1;
	if(ql<=m)
	{
		res+=query(ql,qr,lson);
	}
	if(qr>m)
	{
		res+=query(ql,qr,rson);
	}
	return res;
}

int main() {
	int t, n;
	scanf("%d",&t);
	int casee=1;
	char tmp[8];
	int a,b;
	while (t--) {
		scanf("%d",&n);
		build(1, n, 1);
		printf("Case %d:\n",casee++);
		while(scanf("%s",tmp))
		{
			if(tmp[0]=='E')
			{
				break;
			}
			scanf("%d%d",&a,&b);
			if(tmp[0]=='A')
			{
				update(a,b,1,n,1);
			}
			else if(tmp[0]=='S')
			{
				update(a,-b,1,n,1);
			}
			else
			{
				printf("%d\n",query(a,b,1,n,1));
			}
		}

	}

	return 0;
}

hdu1754 I Hate It

线段树功能:update:单点替换 query:区间最值

#include <bits/stdc++.h>
using namespace std;

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

const int MAXN = 200550;

int sum[MAXN << 2];

void pushup(int rt) {
	sum[rt] = max(sum[rt << 1], sum[rt << 1 | 1]);
}

void build(int l, int r, int rt) {
	if (l == r) {
		scanf("%d", &sum[rt]);
		return;
	}
	int m = (l + r) >> 1;
	build(lson);
	build(rson);
	pushup(rt);
}

void update(int pos, int res, int l, int r, int rt) {
	if (l == r) {
		sum[rt] = res;
		return;
	}
	int m = (l + r) >> 1;
	if (pos <= m) {
		update(pos, res, lson);
	} else {
		update(pos, res, rson);
	}
	pushup(rt);
}

int query(int ql, int qr, int l, int r, int rt) {
	if (ql <= l && r <= qr) {
		return sum[rt];
	}
	int res = 0;
	int m = (l + r) >> 1;
	if (ql <= m) {
		res = max(res, query(ql, qr, lson));
	}
	if (qr > m) {
		res = max(res, query(ql, qr, rson));
	}
	return res;
}

int main() {
	int n, m;
	int a, b;
	while (~scanf("%d%d", &n, &m)) {
		build(1, n, 1);
		char tmp;
		while (m--) {
			cin >> tmp;
			scanf("%d%d", &a, &b);
			if (tmp == 'U') {
				update(a, b, 1, n, 1);
			} else {
				printf("%d\n", query(a, b, 1, n, 1));
			}

		}

	}

	return 0;
}

hdu1394 Minimum Inversion Number

题意:求 Inversion 后的最小逆序数
思路:用 O(nlogn)复杂度求出最初逆序数后,就可以用 O(1)的复杂度分别递推出其他
解
线段树功能:update:单点增减 query:区间求和

import java.util.*;
import java.math.*;

public class Main {
	static int MAXN = 5050;
	static int[] sum = new int[MAXN << 2];

	public static void pushup(int rt) {
		sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
	}

	public static void bulid(int l, int r, int rt) {
		sum[rt] = 0;
		if (r == l) {
			return;
		}
		int m = (l + r) >> 1;
		bulid(l, m, rt << 1);
		bulid(m + 1, r, rt << 1 | 1);
		pushup(rt);
	}

	public static void update(int add, int l, int r, int rt) {
		if (l == r) {
			sum[rt]++;
			return;
		}
		int m = (l + r) >> 1;
		if (add <= m) {
			update(add, l, m, rt << 1);
		} else {
			update(add, m + 1, r, rt << 1 | 1);
		}
		pushup(rt);
	}

	public static int query(int L, int R, int l, int r, int rt) {
		if (L <= l && r <= R) {
			return sum[rt];
		}
		int res = 0;
		int m = (l + r) >> 1;
		if (L <= m) {
			res += query(L, R, l, m, rt << 1);
		}
		if (R > m) {
			res += query(L, R, m + 1, r, rt << 1 | 1);
		}
		return res;
	}

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int n;
		int[] a = new int[5050];
		while (cin.hasNext()) {
			n = cin.nextInt();
			bulid(0, n - 1, 1);
			int sum = 0;
			for (int i = 0; i < n; ++i) {
				a[i] = cin.nextInt();
				sum += query(a[i], n - 1, 0, n - 1, 1);
				update(a[i], 0, n - 1, 1);
			}
			int ans = sum;
			for (int i = 0; i < n; ++i) {
				sum += n - a[i] - a[i] - 1;
				ans = Math.min(ans, sum);
			}

			System.out.println(ans);

		}

		cin.close();
	}

}