线段树、树状数组、归并排序模板
目录
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;
}本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2024-04-21，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录