3109. Find the Index of Permutation

• Time: $O(n\log n)$
• Space: $O(n)$

C++JavaPython

class FenwickTree {
 public:
  FenwickTree(int n) : sums(n + 1) {}

  void add(int i, int delta) {
    while (i < sums.size()) {
      sums[i] += delta;
      i += lowbit(i);
    }
  }

  int get(int i) const {
    int sum = 0;
    while (i > 0) {
      sum += sums[i];
      i -= lowbit(i);
    }
    return sum;
  }

 private:
  vector<int> sums;

  static inline int lowbit(int i) {
    return i & -i;
  }
};

class Solution {
 public:
  int getPermutationIndex(vector<int>& perm) {
    constexpr int kMod = 1'000'000'007;
    const int n = perm.size();
    int ans = 0;
    FenwickTree tree(n);
    vector<int> fact(n + 1, 1);  // fact[i] := i!

    for (int i = 2; i <= n; ++i)
      fact[i] = (fact[i - 1] * static_cast<long>(i)) % kMod;

    for (int i = 0; i < n; ++i) {
      const int num = perm[i];
      // the number of unused numbers less than `num`
      const int unusedNums = num - 1 - tree.get(num - 1);
      const int suffixLength = fact[n - 1 - i];
      ans = (ans + unusedNums * static_cast<long>(suffixLength)) % kMod;
      tree.add(num, 1);
    }

    return ans;
  }
};

class FenwickTree {
  public FenwickTree(int n) {
    sums = new int[n + 1];
  }

  public void add(int i, int delta) {
    while (i < sums.length) {
      sums[i] += delta;
      i += lowbit(i);
    }
  }

  public int get(int i) {
    int sum = 0;
    while (i > 0) {
      sum += sums[i];
      i -= lowbit(i);
    }
    return sum;
  }

  private int[] sums;

  private static int lowbit(int i) {
    return i & -i;
  }
}

class Solution {
  public int getPermutationIndex(int[] perm) {
    final int kMod = 1_000_000_007;
    final int n = perm.length;
    int ans = 0;
    FenwickTree tree = new FenwickTree(n);
    int[] fact = new int[n + 1]; // fact[i] := i!
    Arrays.fill(fact, 1);

    for (int i = 2; i <= n; ++i)
      fact[i] = (int) ((fact[i - 1] * (long) i) % kMod);

    for (int i = 0; i < n; ++i) {
      final int num = perm[i];
      // the number of unused numbers less than `num`
      final int unusedNums = num - 1 - tree.get(num - 1);
      final int suffixLength = fact[n - 1 - i];
      ans = (int) ((ans + unusedNums * (long) suffixLength) % kMod);
      tree.add(num, 1);
    }

    return ans;
  }
}

class FenwickTree:
  def __init__(self, n: int):
    self.sums = [0] * (n + 1)

  def add(self, i: int, delta: int) -> None:
    while i < len(self.sums):
      self.sums[i] += delta
      i += FenwickTree.lowbit(i)

  def get(self, i: int) -> int:
    summ = 0
    while i > 0:
      summ += self.sums[i]
      i -= FenwickTree.lowbit(i)
    return summ

  @staticmethod
  def lowbit(i: int) -> int:
    return i & -i


class Solution:
  def getPermutationIndex(self, perm: list[int]) -> int:
    kMod = 1_000_000_007
    n = len(perm)
    ans = 0
    tree = FenwickTree(n)
    fact = [1] * (n + 1)  # fact[i] := i!

    for i in range(2, n + 1):
      fact[i] = (fact[i - 1] * i) % kMod

    for i, num in enumerate(perm):
      # the number of unused numbers less than `num`
      unusedNums = num - 1 - tree.get(num - 1)
      suffixLength = fact[n - 1 - i]
      ans += unusedNums * suffixLength
      ans %= kMod
      tree.add(num, 1)

    return ans