平方分割

[tipstar0125]

参考：https://kujira16.hateblo.jp/entry/2016/12/15/000000

• 1つのバケット全体に対する質問・変更クエリはO(1)か？
• バケットの中に対する質問・変更クエリはO(√N)か？

[tipstar0125]

RSQ(Range Sum Query)

問題：https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_B 解答：https://onlinejudge.u-aizu.ac.jp/solutions/problem/DSL_2_B/review/8782611/tipstar0125/Rust

• dataを加算更新して、bucket(sum)をO(√N)で再計算

struct SqrtDecomposition {
    N: usize,
    sqrtN: usize,
    K: usize,
    data: Vec<usize>,
    bucket: Vec<usize>,
}

impl SqrtDecomposition {
    fn new(N: usize) -> Self {
        let mut sqrtN = 1;
        while sqrtN * sqrtN <= N {
            sqrtN += 1;
        }
        let K = (N + sqrtN - 1) / sqrtN;
        SqrtDecomposition {
            N,
            K,
            sqrtN,
            data: vec![0; K * sqrtN],
            bucket: vec![0; K],
        }
    }
    fn add(&mut self, pos: usize, x: usize) {
        let k = pos / self.sqrtN;
        self.data[pos] += x;
        let mut s = 0;
        for i in k * self.sqrtN..(k + 1) * self.sqrtN {
            s += self.data[i];
        }
        self.bucket[k] = s;
    }
    fn query(&self, l: usize, r: usize) -> usize {
        let mut ret = 0;
        for k in 0..self.K {
            let ll = k * self.sqrtN;
            let rr = (k + 1) * self.sqrtN;
            if rr <= l || r <= ll {
                continue;
            } else if l <= ll && rr <= r {
                ret += self.bucket[k];
            } else {
                for i in l.max(ll)..r.min(rr) {
                    ret += self.data[i];
                }
            }
        }
        ret
    }
}

[tipstar0125]

RMQ(Range Minimum Query)

問題：https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_A 解答：https://onlinejudge.u-aizu.ac.jp/solutions/problem/DSL_2_A/review/8782760/tipstar0125/Rust

• dataを更新して、bucket(min)をO(√N)で再計算

struct SqrtDecomposition {
    N: usize,
    sqrtN: usize,
    K: usize,
    data: Vec<usize>,
    bucket: Vec<usize>,
}

impl SqrtDecomposition {
    const INF: usize = (1 << 31) - 1;
    fn new(N: usize) -> Self {
        let mut sqrtN = 1;
        while sqrtN * sqrtN <= N {
            sqrtN += 1;
        }
        let K = (N + sqrtN - 1) / sqrtN;
        SqrtDecomposition {
            N,
            K,
            sqrtN,
            data: vec![Self::INF; K * sqrtN],
            bucket: vec![Self::INF; K],
        }
    }
    fn update(&mut self, pos: usize, x: usize) {
        let k = pos / self.sqrtN;
        self.data[pos] = x;
        let mut m = Self::INF;
        for i in k * self.sqrtN..(k + 1) * self.sqrtN {
            m = m.min(self.data[i])
        }
        self.bucket[k] = m;
    }
    fn query(&self, l: usize, r: usize) -> usize {
        let mut ret = Self::INF;
        for k in 0..self.K {
            let ll = k * self.sqrtN;
            let rr = (k + 1) * self.sqrtN;
            if rr <= l || r <= ll {
                continue;
            } else if l <= ll && rr <= r {
                ret = ret.min(self.bucket[k])
            } else {
                for i in l.max(ll)..r.min(rr) {
                    ret = ret.min(self.data[i]);
                }
            }
        }
        ret
    }
}

[tipstar0125]

RAQ(Range Add Query)

問題：https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_E 解答：https://onlinejudge.u-aizu.ac.jp/solutions/problem/DSL_2_E/review/8782866/tipstar0125/Rust

struct SqrtDecomposition {
    N: usize,
    sqrtN: usize,
    K: usize,
    data: Vec<usize>,
    bucket: Vec<usize>,
}

impl SqrtDecomposition {
    fn new(N: usize) -> Self {
        let mut sqrtN = 1;
        while sqrtN * sqrtN <= N {
            sqrtN += 1;
        }
        let K = (N + sqrtN - 1) / sqrtN;
        SqrtDecomposition {
            N,
            K,
            sqrtN,
            data: vec![0; K * sqrtN],
            bucket: vec![0; K],
        }
    }
    fn add(&mut self, l: usize, r: usize, x: usize) {
        for k in 0..self.K {
            let ll = k * self.sqrtN;
            let rr = (k + 1) * self.sqrtN;
            if rr <= l || r <= ll {
                continue;
            } else if l <= ll && rr <= r {
                self.bucket[k] += x;
            } else {
                for i in l.max(ll)..r.min(rr) {
                    self.data[i] += x;
                }
            }
        }
    }
    fn query(&self, pos: usize) -> usize {
        let k = pos / self.sqrtN;
        self.data[pos] + self.bucket[k]
    }
}

[tipstar0125]

RUQ(Range Update Query)

問題：https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_D 解答：https://onlinejudge.u-aizu.ac.jp/solutions/problem/DSL_2_D/review/8783107/tipstar0125/Rust

struct SqrtDecomposition {
    N: usize,
    sqrtN: usize,
    K: usize,
    data: Vec<usize>,
    bucket: Vec<usize>,
    lazy: Vec<bool>,
}

impl SqrtDecomposition {
    const INF: usize = (1 << 31) - 1;
    fn new(N: usize) -> Self {
        let mut sqrtN = 1;
        while sqrtN * sqrtN <= N {
            sqrtN += 1;
        }
        let K = (N + sqrtN - 1) / sqrtN;
        SqrtDecomposition {
            N,
            K,
            sqrtN,
            data: vec![Self::INF; K * sqrtN],
            bucket: vec![0; K],
            lazy: vec![false; K],
        }
    }
    fn eval(&mut self, k: usize) {
        if self.lazy[k] {
            for i in k * self.sqrtN..(k + 1) * self.sqrtN {
                self.data[i] = self.bucket[k];
            }
            self.lazy[k] = false;
        }
    }
    fn update(&mut self, l: usize, r: usize, x: usize) {
        for k in 0..self.K {
            let ll = k * self.sqrtN;
            let rr = (k + 1) * self.sqrtN;
            if rr <= l || r <= ll {
                continue;
            } else if l <= ll && rr <= r {
                self.bucket[k] = x;
                self.lazy[k] = true;
            } else {
                self.eval(k);
                for i in l.max(ll)..r.min(rr) {
                    self.data[i] = x;
                }
            }
        }
    }
    fn query(&mut self, pos: usize) -> usize {
        let k = pos / self.sqrtN;
        self.eval(k);
        self.data[pos]
    }
}

[tipstar0125]

RSQ and RAQ

問題：https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_G 解答：https://onlinejudge.u-aizu.ac.jp/solutions/problem/DSL_2_G/review/8783354/tipstar0125/Rust

struct SqrtDecomposition {
    N: usize,
    sqrtN: usize,
    K: usize,
    data: Vec<usize>,
    bucket_add: Vec<usize>,
    bucket_sum: Vec<usize>,
}

impl SqrtDecomposition {
    fn new(N: usize) -> Self {
        let mut sqrtN = 1;
        while sqrtN * sqrtN <= N {
            sqrtN += 1;
        }
        let K = (N + sqrtN - 1) / sqrtN;
        SqrtDecomposition {
            N,
            K,
            sqrtN,
            data: vec![0; K * sqrtN],
            bucket_add: vec![0; K],
            bucket_sum: vec![0; K],
        }
    }
    fn add(&mut self, l: usize, r: usize, x: usize) {
        for k in 0..self.K {
            let ll = k * self.sqrtN;
            let rr = (k + 1) * self.sqrtN;
            if rr <= l || r <= ll {
                continue;
            } else if l <= ll && rr <= r {
                self.bucket_add[k] += x;
            } else {
                for i in l.max(ll)..r.min(rr) {
                    self.data[i] += x;
                    self.bucket_sum[k] += x;
                }
            }
        }
    }
    fn query(&self, l: usize, r: usize) -> usize {
        let mut ret = 0;
        for k in 0..self.K {
            let ll = k * self.sqrtN;
            let rr = (k + 1) * self.sqrtN;
            if rr <= l || r <= ll {
                continue;
            } else if l <= ll && rr <= r {
                ret += self.bucket_sum[k];
                ret += self.bucket_add[k] * self.sqrtN;
            } else {
                for i in l.max(ll)..r.min(rr) {
                    ret += self.data[i];
                    ret += self.bucket_add[k];
                }
            }
        }
        ret
    }
}

[tipstar0125]

RUQ and RMQ

問題：https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_F 解答：https://onlinejudge.u-aizu.ac.jp/solutions/problem/DSL_2_F/review/8788542/tipstar0125/Rust

struct SqrtDecomposition {
    N: usize,
    sqrtN: usize,
    K: usize,
    data: Vec<usize>,
    bucket_update: Vec<usize>,
    bucket_min: Vec<usize>,
    lazy: Vec<bool>,
}

impl SqrtDecomposition {
    const INF: usize = (1 << 31) - 1;
    fn new(N: usize) -> Self {
        let mut sqrtN = 1;
        while sqrtN * sqrtN <= N {
            sqrtN += 1;
        }
        let K = (N + sqrtN - 1) / sqrtN;
        SqrtDecomposition {
            N,
            K,
            sqrtN,
            data: vec![Self::INF; K * sqrtN],
            bucket_update: vec![0; K],
            bucket_min: vec![Self::INF; K],
            lazy: vec![false; K],
        }
    }
    fn eval(&mut self, k: usize) {
        if self.lazy[k] {
            for i in k * self.sqrtN..(k + 1) * self.sqrtN {
                self.data[i] = self.bucket_update[k];
            }
            self.lazy[k] = false;
        }
    }
    fn update(&mut self, l: usize, r: usize, x: usize) {
        for k in 0..self.K {
            let ll = k * self.sqrtN;
            let rr = (k + 1) * self.sqrtN;
            if rr <= l || r <= ll {
                continue;
            } else if l <= ll && rr <= r {
                self.bucket_update[k] = x;
                self.bucket_min[k] = x;
                self.lazy[k] = true;
            } else {
                self.eval(k);
                for i in l.max(ll)..r.min(rr) {
                    self.data[i] = x;
                }
                let mut m = Self::INF;
                for i in ll..rr {
                    m = m.min(self.data[i]);
                }
                self.bucket_min[k] = m;
            }
        }
    }
    fn query(&mut self, l: usize, r: usize) -> usize {
        let mut ret = Self::INF;
        for k in 0..self.K {
            let ll = k * self.sqrtN;
            let rr = (k + 1) * self.sqrtN;
            if rr <= l || r <= ll {
                continue;
            } else if l <= ll && rr <= r {
                ret = ret.min(self.bucket_min[k]);
            } else {
                self.eval(k);
                for i in l.max(ll)..r.min(rr) {
                    ret = ret.min(self.data[i]);
                }
            }
        }
        ret
    }
}