Binary Inversion Monoid
(monoid/binary_inversion.hpp)

• View this file on GitHub
• Last update: 2026-07-21 20:17:47+09:00
• Include: #include "monoid/binary_inversion.hpp"

Overview

A monoid for counting the number of 0s, 1s, and inversions (the number of pairs where 1 appears before 0) in a binary array.

Initialization

Use the make(val) helper to initialize leaf nodes, passing either 0 or 1.

Example

#include "ds/segtree/segtree.hpp"
#include "monoid/binary_inversion.hpp"
#include <iostream>
#include <vector>

using BinInv = m1une::monoid::BinaryInversion<long long>;

int main() {
    // Array: [1, 0, 1, 0, 0]
    std::vector<int> A = {1, 0, 1, 0, 0};
    int N = A.size();

    std::vector<BinInv::value_type> init_data(N);
    for (int i = 0; i < N; ++i) {
        init_data[i] = BinInv::make(A[i]);
    }

    m1une::ds::Segtree<BinInv> seg(init_data);

    auto res = seg.prod(0, N);

    std::cout << "Zeros: " << res.zeros << "\n";
    std::cout << "Ones: " << res.ones << "\n";
    std::cout << "Inversions: " << res.inversions << "\n"; // Output: 5

    return 0;
}

Interface and Complexity

This is a stateless algebra tag. Generic data structures use its public value_type, id(), and op(a, b) members. If the type also provides helpers such as make(...) or inv(x), they are described above or in the documented properties.

Each static operation runs in the cost of the underlying operation shown in the properties. Scalar monoids are $O(1)$; monoids whose value_type stores several items, permutations, or matrices scale with that stored size.

Required by

• Range Flip Range Binary Inversion (acted_monoid/range_flip_range_binary_inversion.hpp)

Verified with

• verify/monoid/commutative_flags.test.cpp
• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_MONOID_BINARY_INVERSION_HPP
#define M1UNE_MONOID_BINARY_INVERSION_HPP 1

namespace m1une {
namespace monoid {

template <typename T = long long>
struct BinaryInversionNode {
    long long zeros;
    long long ones;
    T inversions;
};

// Monoid for counting zeros, ones, and inversions (1s before 0s) in a binary array.
template <typename T = long long>
struct BinaryInversion {
    using value_type = BinaryInversionNode<T>;
    static constexpr bool commutative = false;

    // The identity element has 0 zeros, 0 ones, and 0 inversions.
    static constexpr value_type id() {
        return {0, 0, 0};
    }

    // Merges two segments and calculates the new inversions.
    // New inversions = left inversions + right inversions + (ones in left * zeros in right)
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return {a.zeros + b.zeros, a.ones + b.ones, a.inversions + b.inversions + a.ones * b.zeros};
    }

    // Helper to securely create a leaf node from a value (0 or 1).
    static constexpr value_type make(int val) {
        if (val == 0) return {1, 0, 0};
        return {0, 1, 0};
    }
};

}  // namespace monoid
}  // namespace m1une

#endif  // M1UNE_MONOID_BINARY_INVERSION_HPP

#line 1 "monoid/binary_inversion.hpp"



namespace m1une {
namespace monoid {

template <typename T = long long>
struct BinaryInversionNode {
    long long zeros;
    long long ones;
    T inversions;
};

// Monoid for counting zeros, ones, and inversions (1s before 0s) in a binary array.
template <typename T = long long>
struct BinaryInversion {
    using value_type = BinaryInversionNode<T>;
    static constexpr bool commutative = false;

    // The identity element has 0 zeros, 0 ones, and 0 inversions.
    static constexpr value_type id() {
        return {0, 0, 0};
    }

    // Merges two segments and calculates the new inversions.
    // New inversions = left inversions + right inversions + (ones in left * zeros in right)
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return {a.zeros + b.zeros, a.ones + b.ones, a.inversions + b.inversions + a.ones * b.zeros};
    }

    // Helper to securely create a leaf node from a value (0 or 1).
    static constexpr value_type make(int val) {
        if (val == 0) return {1, 0, 0};
        return {0, 1, 0};
    }
};

}  // namespace monoid
}  // namespace m1une

Back to top page