---
url: /algo/7ryx30z6/index.md
---
::: warning 警告
本模板为了便于理解，包含了大量的详细注释以及规范的 `std::` 命名空间前缀。在您将代码复制并提交至相关竞赛或评测平台前，请务必根据个人的编程习惯进行调整，重点建议删除冗余注释并精简代码风格。保留明显的模板特征极易被系统的查重算法或 AIGC 监测机制误标为“人工智能生成内容”，从而对您的评审进度或最终成绩产生不利影响。
:::

## 树状数组

维护区间值的操作，比线段树代码精简，并且支持单点修改和区间查询，使复杂度降低到 $O(\log n)$

```cpp title="Fenwick.cc" :collapsed-lines
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;
}
```

## 线段树

结合了动态开点，区间修改以及区间查询的线段树:

::: code-tabs
@tab 区间修改.cc

```cpp :collapsed-lines
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); }
};
```

@tab 区间查询.cc

```cpp :collapsed-lines
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);
    }
};
```

:::

## 并查集

```cpp title="DSU.cc" :collapsed-lines
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;
    }
};
```

## 分数类

```cpp title="Frac.cc" :collapsed-lines
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;
        }
    }
};
```

## 取模类

```cpp title="ModInt.cc" :collapsed-lines
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 排序

```cpp title="TupleSort.cc" :collapsed-lines
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;
}
```

## 自定义优先队列（传统）

```cpp title="CustomPQ(Traditional).cc" :collapsed-lines
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）

```cpp title="CustomPQ(lambda).cc" :collapsed-lines
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;
}
```

## 自定义（多重）集合（传统）

```cpp title="CustomMultiset(T).cc" :collapsed-lines
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）

```cpp title="CustomMultiset(L).cc" :collapsed-lines
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);
```