线段树、树状数组、归并排序模板

用户11039529

发布于 2024-04-25 10:51:57

10300

代码可运行

文章被收录于专栏：算法学习日常算法学习日常

运行总次数：0

代码可运行

P3374 【模板】树状数组 1

P3372 【模板】线段树 1

P1177 【模板】排序

P3374 【模板】树状数组 1

题目链接：https://www.luogu.com.cn/problem/P3374

//树状数组
//基本构成:lowbit();//得到最低位的1			change();//向后修改		query();//向前修改

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <functional>
#include <climits>

#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl "\n"

using namespace std;
typedef long long ll;

const int N = 5e5 + 5;
const int M = 5e5 + 5;

int n, m;
int s[N];//前缀和

//得到最低位的1
int lowbit(int x)
{
	return x & (-x);
}

//向后修改:修改后面的前缀和
void change(int i, int k)
{
	while (i <= n)
	{
		s[i] += k;
		i = i + lowbit(i);//因为是向后修改，所以是加，终止条件为 > n
	}
}

int query(int x)
{
	int sum = 0;
	while (x)
	{
		sum += s[x];
		x -= lowbit(x);//向前修改，所以是 - ，而且终止条件为x == 0
	}
	return sum;
}

int main()
{
	quickio;
	cin >> n >> m;

	int k;
	//向后修改
	for (int i = 1; i <= n; i++)
	{
		cin >> k;
		change(i, k);
	}

	//向前修改
	int x, y, z;
	for (int i = 0; i < m; i++)
	{
		cin >> x >> y >> z;
		if (x == 1)
		{
			//影响了后面
			change(y, z);
		}
		else
		{
			//差分
			cout << query(z) - query(y - 1) << endl;
		}
	}

	return 0;
}

线段树

P3372 【模板】线段树 1

题目链接：https://www.luogu.com.cn/problem/P3372

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <functional>
#include <climits>

#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl "\n"

using namespace std;
typedef long long ll;

#define lc (2*p)
#define rc (2*p+1)

const int N = 1e5 + 5;
const int M = 1e5 + 5;

int a[N];

struct node
{
    int l;
    int r;
    ll sum;
    ll add;
}tr[4 * N];/*4倍*/

//更新
void pushup(int p)
{
    tr[p].sum = tr[lc].sum + tr[rc].sum;
}

//建树
void bulid(int p, int l, int r)
{
    tr[p] = { l, r, a[l], 0 };
    if (l == r)
        return;

    int mid = (l + r) / 2;
    bulid(lc, l, mid);
    bulid(rc, mid + 1, r);
    pushup(p);
}

//把add（懒标记传下去）
void pushdown(int p)
{
    if (tr[p].add)
    {
        tr[lc].add += tr[p].add;
        tr[rc].add += tr[p].add;
        tr[lc].sum += tr[p].add * (tr[lc].r - tr[lc].l + 1);
        tr[rc].sum += tr[p].add * (tr[rc].r - tr[rc].l + 1);
        tr[p].add = 0;/**/
    }
}

ll query(int p, int x, int y)
{
    if (tr[p].l >= x && tr[p].r <= y)
    {
        return tr[p].sum;
    }

    ll sum = 0;
    int mid = (tr[p].l + tr[p].r) / 2;
    //只要会去下一层，就要pushdown，然后pushup回溯
    pushdown(p);
    if (x <= mid)
        sum += query(lc, x, y);
    if (y > mid)
        sum += query(rc, x, y);
    pushup(p);
    return sum;
}

//给[x, y]加上k
void change(int p, int x, int y, int k)
{
    if (x <= tr[p].l && y >= tr[p].r)
    {
        tr[p].sum += k * (tr[p].r - tr[p].l + 1);
        tr[p].add += k;
        return;
    }
    //只要会去下一层，就要pushdown，然后pushup回溯
    pushdown(p);
    int mid = (tr[p].l + tr[p].r) / 2;
    if (x <= mid)
        change(lc, x, y, k);
    if (y > mid)
        change(rc, x, y, k);
    pushup(p);
}

int main()
{
    quickio;
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    bulid(1, 1, n);

    int q, x, y, k;
    for (int i = 0; i < m; i++)
    {
        cin >> q;
        if (q == 1)
        {
            cin >> x >> y >> k;
			change(1, x, y, k);//给区间[x, y]加上k
        }
        else
        {
            cin >> x >> y;
            cout << query(1, x, y) << endl;//求区间和
        }
    }
}

P1177 【模板】排序

题目链接：https://www.luogu.com.cn/problem/P1177

//归并排序：对数组不断等差拆分，直到一个数的长度，回溯是，按升序合并左右两段；
// 先判断终止条件，再拆分，i指向左枝的第一个元素，j指向右枝的第一个元素，k指向根节点第一个位置

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <functional>
#include <climits>

#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl "\n"

using namespace std;
typedef long long ll;

const int N = 1e5 + 5;

int a[N], b[N];//被排序的数组，临时数组

void msort(int l, int r)
{
	if (l == r)//已经分到只有一个了
		return;

	int mid = (l + r) / 2;
	msort(l, mid);
	msort(mid + 1, r);

	int i = l, j = mid + 1, k = l;
	while (i <= mid && j <= r)
	{
		if (a[i] <= a[j])
			b[k++] = a[i++];
		else
			b[k++] = a[j++];
	}

	while (i <= mid)
		b[k++] = a[i++];
	while (j <= r)
		b[k++] = a[j++];

	for (int i = l; i <= r; i++)
		a[i] = b[i];
}

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	msort(1, n);
	for (int i = 1; i <= n; i++)
		cout << a[i] << " ";
	cout << endl;
	return 0;
}