数据结构
约 2746 字大约 9 分钟
2026-01-23
警告
本模板为了便于理解,包含了大量的详细注释以及规范的 std:: 命名空间前缀。在您将代码复制并提交至相关竞赛或评测平台前,请务必根据个人的编程习惯进行调整,重点建议删除冗余注释并精简代码风格。保留明显的模板特征极易被系统的查重算法或 AIGC 监测机制误标为“人工智能生成内容”,从而对您的评审进度或最终成绩产生不利影响。
树状数组
维护区间值的操作,比线段树代码精简,并且支持单点修改和区间查询,使复杂度降低到 O(logn)
Fenwick.cc
template <typename T>
struct Fenwick
{
int n;
std::vector<T> a;
Fenwick(int n_ = 0)
{
init(n_);
}
void init(int n_)
{
n = n_;
a.assign(n, T{});
}
void add(int x, const T &v)
{
for (int i = x + 1; i <= n; i += i & -i)
{
a[i - 1] = a[i - 1] + v;
}
}
T sum(int x)
{
T ans{};
for (int i = x; i > 0; i -= i & -i)
{
ans = ans + a[i - 1];
}
return ans;
}
T rangeSum(int l, int r)
{
return sum(r) - sum(l);
}
// 不超过 k 的最大前缀和索引为多少,例如原数组 [1,2,3,4],前缀和数组 [1,3,6,10],select(5)=2
int select(const T &k)
{
int x = 0;
T cur{};
for (int i = 1 << std::__lg(n); i; i /= 2)
{
if (x + i <= n && cur + a[x + i - 1] <= k)
{
x += i;
cur = cur + a[x - 1];
}
}
return x;
}
};
int main()
{
Fenwick<int> f(10);
f.add(3, 4);
int res = f.rangeSum(1, 9);
std::cout << res; // 4
return 0;
}线段树
结合了动态开点,区间修改以及区间查询的线段树:
区间修改.cc
using namespace std;
template <typename T>
class SegTreeLazyRangeSet
{
vector<T> tree, lazy;
vector<T> *arr;
vector<bool> ifLazy;
int n, root, n4, end;
void maintain(int cl, int cr, int p)
{
int cm = cl + (cr - cl) / 2;
if (cl != cr && ifLazy[p])
{
lazy[p * 2] = lazy[p], ifLazy[p * 2] = 1;
lazy[p * 2 + 1] = lazy[p], ifLazy[p * 2 + 1] = 1;
tree[p * 2] = lazy[p] * (cm - cl + 1);
tree[p * 2 + 1] = lazy[p] * (cr - cm);
lazy[p] = 0;
ifLazy[p] = 0;
}
}
T range_sum(int l, int r, int cl, int cr, int p)
{
if (l <= cl && cr <= r)
return tree[p];
int m = cl + (cr - cl) / 2;
T sum = 0;
maintain(cl, cr, p);
if (l <= m)
sum += range_sum(l, r, cl, m, p * 2);
if (r > m)
sum += range_sum(l, r, m + 1, cr, p * 2 + 1);
return sum;
}
void range_set(int l, int r, T val, int cl, int cr, int p)
{
if (l <= cl && cr <= r)
{
lazy[p] = val;
ifLazy[p] = 1;
tree[p] = (cr - cl + 1) * val;
return;
}
int m = cl + (cr - cl) / 2;
maintain(cl, cr, p);
if (l <= m)
range_set(l, r, val, cl, m, p * 2);
if (r > m)
range_set(l, r, val, m + 1, cr, p * 2 + 1);
tree[p] = tree[p * 2] + tree[p * 2 + 1];
}
void build(int s, int t, int p)
{
if (s == t)
{
tree[p] = (*arr)[s];
return;
}
int m = s + (t - s) / 2;
build(s, m, p * 2);
build(m + 1, t, p * 2 + 1);
tree[p] = tree[p * 2] + tree[p * 2 + 1];
}
public:
explicit SegTreeLazyRangeSet<T>(vector<T> v)
{
n = v.size();
n4 = n * 4;
tree = vector<T>(n4, 0);
lazy = vector<T>(n4, 0);
ifLazy = vector<bool>(n4, 0);
arr = &v;
end = n - 1;
root = 1;
build(0, end, 1);
arr = nullptr;
}
void show(int p, int depth = 0)
{
if (p > n4 || tree[p] == 0)
return;
show(p * 2, depth + 1);
for (int i = 0; i < depth; ++i)
putchar('\t');
printf("%d:%d\n", tree[p], lazy[p]);
show(p * 2 + 1, depth + 1);
}
T range_sum(int l, int r) { return range_sum(l, r, 0, end, root); }
void range_set(int l, int r, T val) { range_set(l, r, val, 0, end, root); }
};区间查询.cc
using namespace std;
template <typename T> class SegTreeLazyRangeMin // 类名改为更合适的Min
{
vector<T> tree, lazy;
vector<T>* arr;
vector<bool> ifLazy;
int n, root, n4, end;
void maintain(int cl, int cr, int p)
{
int cm = cl + (cr - cl) / 2;
if (cl != cr && ifLazy[p])
{
lazy[p * 2] = lazy[p], ifLazy[p * 2] = 1;
lazy[p * 2 + 1] = lazy[p], ifLazy[p * 2 + 1] = 1;
tree[p * 2] = lazy[p]; // 最小值直接等于赋值值
tree[p * 2 + 1] = lazy[p]; // 最小值直接等于赋值值
lazy[p] = 0;
ifLazy[p] = 0;
}
}
T range_min(int l, int r, int cl, int cr, int p)
{
if (l <= cl && cr <= r)
return tree[p];
int m = cl + (cr - cl) / 2;
T min_val = numeric_limits<T>::max(); // 初始化为最大值
maintain(cl, cr, p);
if (l <= m)
min_val = min(min_val, range_min(l, r, cl, m, p * 2));
if (r > m)
min_val = min(min_val, range_min(l, r, m + 1, cr, p * 2 + 1));
return min_val;
}
void range_set(int l, int r, T val, int cl, int cr, int p)
{
if (l <= cl && cr <= r)
{
lazy[p] = val;
ifLazy[p] = 1;
tree[p] = val; // 最小值直接等于赋值值
return;
}
int m = cl + (cr - cl) / 2;
maintain(cl, cr, p);
if (l <= m)
range_set(l, r, val, cl, m, p * 2);
if (r > m)
range_set(l, r, val, m + 1, cr, p * 2 + 1);
// 更新父节点为两个子节点的最小值
tree[p] = min(tree[p * 2], tree[p * 2 + 1]);
}
void build(int s, int t, int p)
{
if (s == t)
{
tree[p] = (*arr)[s];
return;
}
int m = s + (t - s) / 2;
build(s, m, p * 2);
build(m + 1, t, p * 2 + 1);
// 取两个子节点的最小值
tree[p] = min(tree[p * 2], tree[p * 2 + 1]);
}
public:
explicit SegTreeLazyRangeMin<T>(vector<T> v)
{
n = v.size();
n4 = n * 4;
tree = vector<T>(n4, 0);
lazy = vector<T>(n4, 0);
ifLazy = vector<bool>(n4, 0);
arr = &v;
end = n - 1;
root = 1;
build(0, end, 1);
arr = nullptr;
}
void show(int p, int depth = 0)
{
if (p > n4 || tree[p] == 0)
return;
show(p * 2, depth + 1);
for (int i = 0; i < depth; ++i)
putchar('\t');
printf("%d:%d\n", tree[p], lazy[p]);
show(p * 2 + 1, depth + 1);
}
// 查询区间最小值
T range_min(int l, int r)
{
return range_min(l, r, 0, end, root);
}
// 区间赋值操作
void range_set(int l, int r, T val)
{
range_set(l, r, val, 0, end, root);
}
};并查集
DSU.cc
struct DSU
{
std::vector<int> f, siz;
int setCount; // 不同集合的数量
DSU() : setCount(0) {}
DSU(int n)
{
init(n);
}
void init(int n)
{
f.resize(n);
std::iota(f.begin(), f.end(), 0);
siz.assign(n, 1);
setCount = n; // 初始时每个元素都是一个集合
}
int find(int x)
{
while (x != f[x])
{
x = f[x] = f[f[x]];
}
return x;
}
bool same(int x, int y)
{
return find(x) == find(y);
}
bool merge(int x, int y)
{
x = find(x);
y = find(y);
if (x == y)
{
return false;
}
if (siz[x] < siz[y])
{
std::swap(x, y);
}
siz[x] += siz[y];
f[y] = x;
setCount--; // 合并后集合数量减少1
return true;
}
int size(int x)
{
return siz[find(x)];
}
// 获取不同集合的数量
int count() const
{
return setCount;
}
};分数类
Frac.cc
template <class T>
struct Frac
{
T num;
T den;
Frac(T num_, T den_) : num(num_), den(den_)
{
if (den < 0)
{
den = -den;
num = -num;
}
}
Frac() : Frac(0, 1) {}
Frac(T num_) : Frac(num_, 1) {}
explicit operator double() const
{
return 1. * num / den;
}
Frac &operator+=(const Frac &rhs)
{
num = num * rhs.den + rhs.num * den;
den *= rhs.den;
return *this;
}
Frac &operator-=(const Frac &rhs)
{
num = num * rhs.den - rhs.num * den;
den *= rhs.den;
return *this;
}
Frac &operator*=(const Frac &rhs)
{
num *= rhs.num;
den *= rhs.den;
return *this;
}
Frac &operator/=(const Frac &rhs)
{
num *= rhs.den;
den *= rhs.num;
if (den < 0)
{
num = -num;
den = -den;
}
return *this;
}
friend Frac operator+(Frac lhs, const Frac &rhs)
{
return lhs += rhs;
}
friend Frac operator-(Frac lhs, const Frac &rhs)
{
return lhs -= rhs;
}
friend Frac operator*(Frac lhs, const Frac &rhs)
{
return lhs *= rhs;
}
friend Frac operator/(Frac lhs, const Frac &rhs)
{
return lhs /= rhs;
}
friend Frac operator-(const Frac &a)
{
return Frac(-a.num, a.den);
}
friend bool operator==(const Frac &lhs, const Frac &rhs)
{
return lhs.num * rhs.den == rhs.num * lhs.den;
}
friend bool operator!=(const Frac &lhs, const Frac &rhs)
{
return lhs.num * rhs.den != rhs.num * lhs.den;
}
friend bool operator<(const Frac &lhs, const Frac &rhs)
{
return lhs.num * rhs.den < rhs.num * lhs.den;
}
friend bool operator>(const Frac &lhs, const Frac &rhs)
{
return lhs.num * rhs.den > rhs.num * lhs.den;
}
friend bool operator<=(const Frac &lhs, const Frac &rhs)
{
return lhs.num * rhs.den <= rhs.num * lhs.den;
}
friend bool operator>=(const Frac &lhs, const Frac &rhs)
{
return lhs.num * rhs.den >= rhs.num * lhs.den;
}
friend std::ostream &operator<<(std::ostream &os, Frac x)
{
T g = std::gcd(x.num, x.den);
if (x.den == g)
{
return os << x.num / g;
}
else
{
return os << x.num / g << "/" << x.den / g;
}
}
};取模类
ModInt.cc
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;
template <typename T>
constexpr T power(T a, u64 b)
{
T res{1};
for (; b != 0; b /= 2, a *= a)
{
if (b % 2 == 1)
{
res *= a;
}
}
return res;
}
template <u32 P>
constexpr u32 mulMod(u32 a, u32 b)
{
return 1ULL * a * b % P;
}
template <u64 P>
constexpr u64 mulMod(u64 a, u64 b)
{
u64 res = a * b - u64(1.L * a * b / P - 0.5L) * P;
res %= P;
return res;
}
template <typename U, U P>
requires std::unsigned_integral<U>
struct ModIntBase
{
public:
constexpr ModIntBase() : x{0} {}
template <typename T>
requires std::integral<T>
constexpr ModIntBase(T x_) : x{norm(x_ % T{P})}
{
}
constexpr static U norm(U x)
{
if ((x >> (8 * sizeof(U) - 1) & 1) == 1)
{
x += P;
}
if (x >= P)
{
x -= P;
}
return x;
}
constexpr U val() const
{
return x;
}
constexpr ModIntBase operator-() const
{
ModIntBase res;
res.x = norm(P - x);
return res;
}
constexpr ModIntBase inv() const
{
return power(*this, P - 2);
}
constexpr ModIntBase &operator*=(const ModIntBase &rhs) &
{
x = mulMod<P>(x, rhs.val());
return *this;
}
constexpr ModIntBase &operator+=(const ModIntBase &rhs) &
{
x = norm(x + rhs.x);
return *this;
}
constexpr ModIntBase &operator-=(const ModIntBase &rhs) &
{
x = norm(x - rhs.x);
return *this;
}
constexpr ModIntBase &operator/=(const ModIntBase &rhs) &
{
return *this *= rhs.inv();
}
friend constexpr ModIntBase operator*(ModIntBase lhs, const ModIntBase &rhs)
{
lhs *= rhs;
return lhs;
}
friend constexpr ModIntBase operator+(ModIntBase lhs, const ModIntBase &rhs)
{
lhs += rhs;
return lhs;
}
friend constexpr ModIntBase operator-(ModIntBase lhs, const ModIntBase &rhs)
{
lhs -= rhs;
return lhs;
}
friend constexpr ModIntBase operator/(ModIntBase lhs, const ModIntBase &rhs)
{
lhs /= rhs;
return lhs;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const ModIntBase &a)
{
return os << a.val();
}
friend constexpr bool operator==(ModIntBase lhs, ModIntBase rhs)
{
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(ModIntBase lhs, ModIntBase rhs)
{
return lhs.val() != rhs.val();
}
friend constexpr bool operator<(ModIntBase lhs, ModIntBase rhs)
{
return lhs.val() < rhs.val();
}
private:
U x;
};
template <u32 P>
using ModInt = ModIntBase<u32, P>;
template <u64 P>
using ModInt64 = ModIntBase<u64, P>;
constexpr u32 P = 998244353;
using Z = ModInt<P>;自定义 Tuple 排序
TupleSort.cc
bool compareTuple(const std::tuple<int, std::string> &a, const std::tuple<int, std::string> &b)
{
return std::get<0>(a) < std::get<0>(b); // 按第一个元素排序
}
int main()
{
std::vector<std::tuple<int, std::string>> tupleVec = {
std::make_tuple(3, "Three"),
std::make_tuple(1, "One"),
std::make_tuple(2, "Two")};
// 排序
std::sort(tupleVec.begin(), tupleVec.end(), compareTuple);
// 输出结果
for (const auto &tuple : tupleVec)
{
std::cout << std::get<0>(tuple) << " " << std::get<1>(tuple) << std::endl;
}
return 0;
}自定义优先队列(传统)
CustomPQ(Traditional).cc
using namespace std;
priority_queue<int> q; //默认从大到小(大根堆)
priority_queue<int, vector<int>, less<int>> q; //从大到小排序(大根堆)
priority_queue<int, vector<int>, greater<int>> q; //从小到大排序(小根堆)
struct Student
{
string name;
int score;
int age;
};
// 按分数降序排列
struct CompareByScore
{
bool operator()(const Student &a, const Student &b)
{
return a.score < b.score; // 最大堆:返回true表示a的优先级低于b
}
};
// 按分数升序排列
struct CompareByScoreAsc
{
bool operator()(const Student &a, const Student &b)
{
return a.score > b.score; // 最小堆
}
};
// 多级排序:先按分数降序,分数相同按年龄升序
struct CompareMulti
{
bool operator()(const Student &a, const Student &b)
{
if (a.score != b.score)
return a.score < b.score; // 分数高的在前
return a.age > b.age; // 年龄小的在前
}
};
int main()
{
// 使用自定义比较类
priority_queue<Student, vector<Student>, CompareByScore> pq1;
// 或者使用多级排序
priority_queue<Student, vector<Student>, CompareMulti> pq2;
pq2.push({"Alice", 85, 20});
pq2.push({"Bob", 85, 19});
pq2.push({"Charlie", 90, 21});
while (!pq2.empty())
{
auto s = pq2.top();
cout << s.name << " " << s.score << " " << s.age << endl;
pq2.pop();
}
return 0;
}自定义优先队列(lambda)
CustomPQ(lambda).cc
using namespace std;
struct Student
{
string name;
int score;
};
int main()
{
// 使用lambda表达式作为比较函数
auto cmp = [](const Student &a, const Student &b)
{
return a.score < b.score; // 最大堆
};
// 注意:需要指定容器类型和比较器类型
priority_queue<Student, vector<Student>, decltype(cmp)> pq(cmp);
// 也可以这样定义(更简洁的方式)
priority_queue<Student, vector<Student>,
function<bool(const Student &, const Student &)>>
pq2([](const Student &a, const Student &b)
{
return a.score > b.score; // 最小堆
});
pq.push({"Alice", 85});
pq.push({"Bob", 92});
return 0;
}自定义(多重)集合(传统)
CustomMultiset(T).cc
using namespace std;
// 注意和优先队列是相反的
set<int> s; //默认从小到大
set<int, vector<int>, less<int>> q; //从小到大排序
set<int, vector<int>, greater<int>> q; //从大到小排序
struct Person {
string name;
int age;
};
// 自定义比较器
struct PersonComparator {
bool operator()(const Person& a, const Person& b) const {
// 先按年龄降序,年龄相同按名字升序
if (a.age != b.age)
return a.age > b.age; // 注意这里是 >,表示降序
return a.name < b.name;
}
};
// 使用
set<Person, PersonComparator> people1;
multiset<Person, PersonComparator> people2;自定义(多重)集合(lambda)
CustomMultiset(L).cc
using namespace std;
struct Person {
string name;
int age;
};
// 使用decltype和lambda定义比较器
auto cmp = [](const Person& a, const Person& b) {
return a.age < b.age; // 只按年龄升序
};
// 注意:lambda需要指定模板参数
set<Person, decltype(cmp)> people(cmp);
multiset<Person, decltype(cmp)> people_multi(cmp);