树状数组

逆序对

#include 
#include 
#include 
#define int long long
using namespace std;
const int N = 5e5 + 10;
int tr[N], ranks[N], n;
int ans;
struct point
{
	int num, val;
	bool operator<(const point &x) const
	{
		if (val == x.val)
			return num < x.num;
		return val < x.val;
	}
}a[N];

int lowbit(int x)
{
	return x & -x;
}

void add(int idx, int x)
{
	for (int i = idx; i <= n; i += lowbit(i))
		tr[i] += x;
}

int sum(int idx)
{
	int s = 0;
	for (int i = idx; i; i -= lowbit(i))
		s += tr[i];
	return s;
}
signed main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i].val, a[i].num = i;
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++)
		ranks[a[i].num] = i;
	for (int i = 1; i <= n; i++)
	{
		add(ranks[i], 1);
		ans += i - sum(ranks[i]);
	}
	cout << ans << endl;
	return 0;
}

差分实现区间修改，单点查询

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, m;
int tr[N];
int lowbit(int x)
{
	return x & -x;
}

void add(int idx, int k)
{
	for (int i = idx; i < N; i += lowbit(i))
		tr[i] += k;
}

int sum(int idx)
{
	int ans = 0;
	for (int i = idx; i; i -= lowbit(i))
		ans += tr[i];
	return ans;
}
int main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	while(m--)
	{
		int t;
		cin >> t;
		if (t == 1)
		{
			int l, r;
			cin >> l >> r;
			add(l, 1), add(r + 1, -1);
		}
		else
		{
			int x;
			cin >> x;
			cout << (sum(x) & 1) << endl;
		} 
	}
	return 0;
}

前缀最值 + 单点修改

利用二维偏序优化最长上升子序列 \(i

本题求的是最长下降子序列

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 1e9;
int n;
int a[N], f[N], tr[N];
int lowbit(int x)
{
	return x & -x;
}

void update(int x, int k)
{
	for (int i = x; i < N; i += lowbit(i))
		tr[i] = max(tr[i], k);
}

int query(int x)
{
	int ans = 0;
	for (int i = x; i; i -= lowbit(i))
		ans = max(ans, tr[i]);
	return ans;
}
int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d", &n);
		int ans = 1;
		for (int i = 1; i <= n; i++)
			tr[i] = 0;
		for (int i = 1; i <= n; i++)
			scanf("%d", &a[i]), a[i] = n + 1 - a[i];//将逆序对变为正序对
		for (int i = 1; i <= n; i++)
		{
			f[i] = query(a[i]) + 1;
			update(a[i], f[i]);
			ans = max(ans, f[i]);
		}
		printf("%d\n", ans);
		for (int i = 1; i <= n; i++)
			printf("%d ", f[i]);
		puts("");
	}
	return 0;
}

二维树状数组

JSOI2009]计数问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int N = 3e2 + 10;
int n, m, q;
int tr[N][N][110];
int a[N][N];
int lowbit(int x)
{
	return x & -x;
}
void add(int x, int y, int c, int k)
{
	for (int i = x; i < N; i += lowbit(i))
		for (int j = y; j < N; j += lowbit(j))
			tr[i][j][c] += k;
}

int sum(int x, int y, int c)
{
	int ans = 0;
	for (int i = x; i; i -= lowbit(i))
		for (int j = y; j; j -= lowbit(j))
			ans += tr[i][j][c];
	return ans;
}
int main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			int x;
			cin >> x;
			a[i][j] = x;
			add(i, j, x, 1);
		}
	}
	cin >> q;
	while(q--)
	{
		int op;
		cin >> op;
		if (op == 1)
		{
			int x, y, c;
			cin >> x >> y >> c;
			int last = a[x][y];
			add(x, y, c, 1);
			add(x, y, last, -1);
			a[x][y] = c;
		}
		else
		{
			int x1, y1, x2, y2, c;
			cin >> x1 >> x2 >> y1 >> y2 >> c;
			cout << sum(x2, y2, c) - sum(x1-1, y2, c) - sum(x2, y1-1, c) + sum(x1-1, y1-1, c) << endl;
		}
	}
	return 0;
}