1622. Fancy Sequence

Intuition

Lazy segment tree for range add operations and point queries. Operations are add to indices 1..i and add to indices i..n.

Algorithm

1Maintain prefix sum differences. Each operation [l,r,v]: difference[l]+=v, difference[r+1]-=v.
2Get(i): return sum of differences[1..i].

Common Pitfalls

•Mod operation needed. Segment tree or BIT with lazy propagation.

1622.cs

// Approach: Lazy linear transform a*x+b maintained globally; use Fermat's little theorem for modular inverse on GetIndex.
// Time: O(1) per op, O(n) for getIndex Space: O(n)

public class Fancy
{
    // To undo a * val + b and get the original value, we append (val - b) / a.
    // By Fermat's little theorem:
    //   a^(p - 1) ≡ 1 (mod p)
    //   a^(p - 2) ≡ a^(-1) (mod p)
    // So, (val - b) / a ≡ (val - b) * a^(p - 2) (mod p)
    public void Append(int val)
    {
        long x = (val - b + MOD) % MOD;
        vals.Add(x * ModPow(a, MOD - 2) % MOD);
    }

    // If the value is a * val + b, then the value after adding by `inc` will be
    // a * val + b + inc. So, we adjust b to b + inc.
    public void AddAll(int inc)
    {
        b = (b + inc) % MOD;
    }

    // If the value is a * val + b, then the value after multiplying by `m` will
    // be a * m * val + b * m. So, we adjust a to a * m and b to b * m.
    public void MultAll(int m)
    {
        a = (a * m) % MOD;
        b = (b * m) % MOD;
    }

    public int GetIndex(int idx)
    {
        return idx >= vals.Count ? -1 : (int)((a * vals[idx] + b) % MOD);
    }

    private const int MOD = 1_000_000_007;
    // For each `val` in `vals`, it actually represents a * val + b.
    private List<long> vals = new List<long>();
    private long a = 1;
    private long b = 0;

    private long ModPow(long x, long n)
    {
        if (n == 0)
            return 1;
        if (n % 2 == 1)
            return (x * ModPow(x % MOD, n - 1)) % MOD;
        long half = ModPow((x * x) % MOD, n / 2);
        return half % MOD;
    }
}

/**
 * Your Fancy object will be instantiated and called as such:
 * Fancy obj = new Fancy();
 * obj.Append(val);
 * obj.AddAll(inc);
 * obj.MultAll(m);
 * int param_4 = obj.GetIndex(idx);
 */

Was this solution helpful?