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

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

Overview

An Acted Monoid designed for binary arrays (01-strings) to support range bit-flipping operations (inverting $0 \leftrightarrow 1$) and range binary inversion queries (the number of pairs $(i, j)$ such that $i < j$ and $A[i] = 1, A[j] = 0$).

This acted monoid leverages the structure of m1une::monoid::BinaryInversionNode. When a range is flipped, the counts of zeros and ones are swapped. Concurrently, the new number of inversions is computed as the total number of possible pairs minus the old number of inversions: \(\text{new\_inversions} = (\text{zeros} \times \text{ones}) - \text{old\_inversions}\)

Template Parameters

• T: The underlying scalar integer type used to store counts and inversion numbers (e.g., long long).

Data Structure

• using value_type = m1une::monoid::BinaryInversionNode<T>; The state tracked in each segment tree node:
  • zeros: The number of 0s in the segment.
  • ones: The number of 1s in the segment.
  • inversions: The number of pairs where 1 appears before 0.
• using operator_type = bool; A boolean flag representing whether the segment needs to be flipped (true) or not (false).

Element Creation

When initializing the lazy segment tree, you must transform the raw binary values (0 or 1) into valid monoid nodes. Always use the make(val) helper method to securely build the leaf nodes.

static constexpr value_type make(int val)

• Parameters:
  • val: The binary element value (0 or 1).
• Returns: A BinaryInversionNode properly initialized for a single element.

Example

#include "ds/segtree/lazy_segtree.hpp"
#include "acted_monoid/range_flip_range_binary_inversion.hpp"
#include <iostream>
#include <vector>

using AM = m1une::acted_monoid::RangeFlipRangeBinaryInversion<long long>;

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

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

    m1une::ds::LazySegtree<AM> seg(init_nodes);

    // 1. Query entire array inversion count
    // Initial inversions: 5 (index pairs: (0,1), (0,3), (0,4), (2,3), (2,4))
    std::cout << "Initial Inversions: " << seg.all_prod().inversions << "\n"; // Output: 5

    // 2. Range Flip: Invert bits in range [1, 4) -> indices 1, 2, 3
    // A becomes: [1, 1, 0, 1, 0]
    seg.apply(1, 4, true);

    // 3. Query after inversion
    // New inversions: 5 (index pairs: (0,2), (0,4), (1,2), (1,4), (3,4))
    auto res = seg.prod(0, N);
    std::cout << "Zeros: " << res.zeros << ", Ones: " << res.ones << "\n"; // Output: Zeros: 2, Ones: 3
    std::cout << "Updated Inversions: " << res.inversions << "\n";         // Output: 5

    return 0;
}

Interface and Complexity

This is a stateless acted-monoid tag. Lazy data structures use its public value_type, operator_type, id(), op(a, b), op_id(), op_comp(f, g), and mapping(f, x) members. Helpers such as make(...), shifted mappings, or reversal-aware mappings are described above when the header provides them.

The static operations are $O(1)$ for the scalar metadata stored by these range acted monoids, aside from the cost of the underlying arithmetic type.

Depends on

• Binary Inversion Monoid (monoid/binary_inversion.hpp)

Verified with

• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_ACTED_MONOID_RANGE_FLIP_RANGE_BINARY_INVERSION_HPP
#define M1UNE_ACTED_MONOID_RANGE_FLIP_RANGE_BINARY_INVERSION_HPP 1

#include "../monoid/binary_inversion.hpp"

namespace m1une {
namespace acted_monoid {

template <typename T = long long>
struct RangeFlipRangeBinaryInversion {
    using value_type = m1une::monoid::BinaryInversionNode<T>;
    using operator_type = bool;
    static constexpr bool commutative = false;
    static constexpr bool operator_commutative = true;

    static constexpr value_type id() {
        return {0, 0, 0};
    }
    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};
    }

    static constexpr operator_type op_id() {
        return false;
    }
    static constexpr operator_type op_comp(const operator_type& f, const operator_type& g) {
        return f ^ g;
    }

    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        if (!f) return x;
        return {x.ones, x.zeros, x.zeros * x.ones - x.inversions};
    }

    static constexpr value_type make(int val) {
        if (val == 0) return {1, 0, 0};
        return {0, 1, 0};
    }
};

}  // namespace acted_monoid
}  // namespace m1une

#endif  // M1UNE_ACTED_MONOID_RANGE_FLIP_RANGE_BINARY_INVERSION_HPP

#line 1 "acted_monoid/range_flip_range_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


#line 5 "acted_monoid/range_flip_range_binary_inversion.hpp"

namespace m1une {
namespace acted_monoid {

template <typename T = long long>
struct RangeFlipRangeBinaryInversion {
    using value_type = m1une::monoid::BinaryInversionNode<T>;
    using operator_type = bool;
    static constexpr bool commutative = false;
    static constexpr bool operator_commutative = true;

    static constexpr value_type id() {
        return {0, 0, 0};
    }
    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};
    }

    static constexpr operator_type op_id() {
        return false;
    }
    static constexpr operator_type op_comp(const operator_type& f, const operator_type& g) {
        return f ^ g;
    }

    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        if (!f) return x;
        return {x.ones, x.zeros, x.zeros * x.ones - x.inversions};
    }

    static constexpr value_type make(int val) {
        if (val == 0) return {1, 0, 0};
        return {0, 1, 0};
    }
};

}  // namespace acted_monoid
}  // namespace m1une

Back to top page