【Rust】競プロ文脈でジェネリック、トレイトを理解する【二次元累積和】

コンテスト中で忙しい人へ
====

実装した二次元累積和を置いておきます。
半開区間[i0, i1) × [j0, j1)の値の総和を$O(1)$求めます（構築は$O(HW)$）。
半開区間のためi1の行とj1の列は含まれないことに注意してください。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/409742/50cf8080-4ca1-6cee-0641-bcd46d37bad9.png)


num_traitsクレートを使用しているため、<font color="red">AtCoder以外のJudgeでは多分動かない</font>と思います。

<details><summary>コピペして使用してください</summary><div>

```Rust
use cumsum2d::CumSum2D;

pub mod cumsum2d {
    use num_traits::Zero;
    use std::ops::Sub;

    #[derive(Debug, Clone)]
    pub struct CumSum2D<T> {
        pub data: Vec<Vec<T>>,
    }

    impl<T> CumSum2D<T>
        where T: Zero + Copy + Clone + Sub<Output=T>
    {
        pub fn from(input: &Vec<Vec<T>>) -> Self {
            let h = input.len();
            let w = input[0].len();
            let mut data = vec![vec![T::zero(); w + 1]; h + 1];
            for i in 1..=h {
                for j in 1..=w {
                    data[i][j] = data[i - 1][j] + data[i][j - 1] + input[i - 1][j - 1] - data[i - 1][j - 1];
                }
            }
            CumSum2D { data }
        }

        pub fn query(&self, i0: usize, i1: usize, j0: usize, j1: usize) -> T {
            self.data[i1][j1] - self.data[i1][j0] - self.data[i0][j1] + self.data[i0][j0]
        }
    }

    #[test]
    fn test_cumsum2d() {
        let cs = CumSum2D::from(&vec![vec![1, 2, 3, 4], vec![5, 6, 7, 8], vec![9, 10, 11, 12]]);
        assert_eq!(cs.query(0, 3, 0, 4), 78);
        assert_eq!(cs.query(0, 1, 0, 1), 1);
        assert_eq!(cs.query(1, 3, 1, 3), 34);

        // for i64
        let cs = CumSum2D::from(&vec![vec![1i64, 2, 3, 4], vec![5, 6, 7, 8], vec![9, 10, 11, 12]]);
        assert_eq!(cs.query(0, 3, 0, 4), 78i64);

        // for u64
        let cs = CumSum2D::from(&vec![vec![1u64, 2, 3, 4], vec![5, 6, 7, 8], vec![9, 10, 11, 12]]);
        assert_eq!(cs.query(0, 3, 0, 4), 78u64);

        // for usize
        let cs = CumSum2D::from(&vec![vec![1usize, 2, 3, 4], vec![5, 6, 7, 8], vec![9, 10, 11, 12]]);
        assert_eq!(cs.query(0, 3, 0, 4), 78usize);

        // // for f64
        // // Cargo.tomlに以下を追加してね
        // // assert_approx_eq = "1.1.0"
        // use assert_approx_eq::assert_approx_eq;
        // use num_traits::Float;
        // let cs =  CumSum2D::from(&vec![vec![0.1,0.2,0.3,0.4],
        //                                vec![0.5,0.6,0.7,0.8],
        //                                vec![0.9,1.0,1.1,1.2]]);
        // assert_approx_eq!(cs.query(1, 3, 1, 3), 3.4);
    }
}
```

</div></details>


はじめに
=====

先日の[ABC203のD問題](https://atcoder.jp/contests/abc203/tasks/abc203_d)で二次元累積和を使用する問題が出たので、これを機にライブラリとして整備しました。
どうせなら`i64`だけではなく`f64`等にも使えるようにしたいとか考えていたら、実装でいろいろ躓いたので記事にします。

二次元累積和については、以下を参照してください（実装も下記記事に準拠します）。

- [累積和を何も考えずに書けるようにする！](https://qiita.com/drken/items/56a6b68edef8fc605821#4-%E4%BA%8C%E6%AC%A1%E5%85%83%E7%B4%AF%E7%A9%8D%E5%92%8C)


対象読者
=====

- そろそろ自分用の競プロライブラリをつくりたいと思ってる人
- 正直Rustのトレイト、ジェネリックがあやふやな人
- Rustつよつよの人のライブラリをチラ見したら、宇宙語が書いてあってそっと閉じた人


事始め
=====

次の2つのメソッドを持つ構造体を作成することを考えます。

- 二次元ベクタの参照を引数に取り、累積和を構築するメソッド`from`
- 区間[i0, i1) × [j0, j1)の値の総和の返すメソッド`query`

以下が使用イメージです。

```Rust
let a = vec![vec![1, 2, 3, 4], vec![5, 6, 7, 8], vec![9, 10, 11, 12]];
let cs = CumSum2D::from(&a);
println("{}", cs.query(1, 3, 1, 3))  // 34
```

以下に構造体とメソッドのガワを準備しました。`data`に構築した累積和が入ります。
何の前置きもせずジェネリック実装してますが、`T`に`i64`や`f64`が入ると考えれば、それほど理解は難しくないと思います。


```Rust
#[derive(Debug, Clone)]
pub struct CumSum2D<T> {
    pub data: Vec<Vec<T>>,
}

impl<T> CumSum2D<T>
{
    pub fn from(input: &Vec<Vec<T>>) -> Self {
        todo!()  // ①
    }

    pub fn query(&self, i0: usize, i1: usize, j0: usize, j1: usize) -> T {
        todo!()  // ②
    }
}
```

ここから①、②を実装していきます。


トレイト境界
====

①`from`を実装していきます。
インプットが$H$×$W$のベクタとすると、二次元累積和は$(H+1)$×$(W+1)$のベクタになります。
まず、$(H+1)$×$(W+1)$のベクタを0埋めして作成することを考えます。

```Rust
impl<T> CumSum2D<T>
{
    pub fn from(input: &Vec<Vec<T>>) -> Self {
        let h = input.len();
        let w = input[0].len();
        let mut data = vec![vec![0 as T; w + 1]; h + 1];   // エラー
        CumSum2D { data }
    }
}
```

いかにも怪しい実装です。実際にコンパイルが通りません。

エラーメッセージを見て行きましょう。

```
error[E0277]: the trait bound `T: std::clone::Clone` is not satisfied
80 |let mut data = vec![vec![0 as T; w + 1]; h + 1];
   |                         ^^^^^^^^^^^^^^^^^^^^^^ the trait `std::clone::Clone` is not implemented for `T`
```
まず、`T`に対して、`Clone`が実装されてないことを怒られているようです。

今回`T`が対象としたいのは、`i32`や`f64`といったプリミティブな数値型です。
プリミティブな数値型は次の代入に示されるように、値がコピーされます。

```Rust
let a = 1;
let b = a;      // 値渡しで代入される
```

従って、`T`は`Copy + Clone`を条件を必ず満たして欲しいということになります。
このように`T`に制約を課していくことを、トレイト境界（今回の場合、特にジェネリック境界）と言います。

トレイト境界はimplに記載していきます。（二通り書き方があり、今回はwhere句で書いていきます）

```Rust
impl<T> CumSum2D<T>
    where T: Copy + Clone
```


0が欲しい
====

`Copy + Clone`をトレイト境界に定めても、まだまだエラーが出ます。

```
error[E0605]: non-primitive cast: `i32` as `T`
80 |         let mut data = vec![vec![0 as T; w + 1]; h + 1];
   |                                  ^^^^^^
   = note: an `as` expression can only be used to convert between primitive types. Consider using the `From` trait
```

`0`を`T`にキャストするために`From`トレイトを定めないといけないようです。


でも、ちょっと待って下さい。
今回行いたいことは、二次元配列を`0`で埋めることです。
ここで言う`0`とは、`i32`では`0i32`、`f64`では`0.0`、`usize`では`0usize`のことになります。

型に依って適切な`0`が降ってくる仕組みはないかなー？？？
ということで活躍するトレイトが、num_traits::Zeroです。

以下のようにトレイト境界を定めます。

```Rust
use num_traits::Zero;
impl<T> CumSum2D<T>
    where T: Zero + Copy + Clone
```

すると、`T`に対して`zero()`というメソッドが生えてきます。
このメソッドこそが前述した「`i32`では`0i32`、`f64`では`0.0`、`usize`では`0usize`」を返すメソッドとなります。

```Rust
let mut data = vec![vec![T::zero(); w + 1]; h + 1];   // これならOK
```

あとは累積和を構築していくコードを書いて`from`は完成です。

```Rust
impl<T> CumSum2D<T>
    where T: Zero + Copy + Clone
{
    pub fn from(input: &Vec<Vec<T>>) -> Self {
        let h = input.len();
        let w = input[0].len();
        let mut data = vec![vec![0 as T; w + 1]; h + 1];
        for i in 1..=h {
            for j in 1..=w {
                data[i][j] = data[i - 1][j] + data[i][j - 1] + input[i - 1][j - 1] - data[i - 1][j - 1];
            }
        }
        CumSum2D { data }
    }
}
```

演算子のオーバーロードとT::Output
===

この調子で、②の`Query`を実装していきます。

```Rust
impl<T> CumSum2D<T>
    where T: Zero + Copy + Clone
{
    pub fn query(&self, i0: usize, i1: usize, j0: usize, j1: usize) -> T {
        self.data[i1][j1] - self.data[i1][j0] - self.data[i0][j1] + self.data[i0][j0]
    }
}
```

```
error[E0369]: cannot subtract `T` from `T`
  --> src/bin/d.rs:83:84
   |
83 |                 data[i][j] = data[i - 1][j] + data[i][j - 1] + input[i - 1][j - 1] - data[i - 1][j - 1];
   |                              ----------------------------------------------------- ^ ------------------ T
   |                              |
   |                              T
   = note: `T` might need a bound for `std::ops::Sub`
```

コンパイラに怒られました。
どうやら`T`に対して引き算が行えることを保証してあげなければいけないようです。
Rustくんは細かいなぁ…


```Rust
use std::ops::Sub;
impl<T> CumSum2D<T>
    where T: Zero + Copy + Clone + Sub
```

```
error[E0308]: mismatched types
  --> src/bin/d.rs:83:30
   |
83 |                 data[i][j] = data[i - 1][j] + data[i][j - 1] + input[i - 1][j - 1] - data[i - 1][j - 1];
   |                              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected type parameter `T`, found associated type
   |
   = note: expected type parameter `T`
             found associated type `<T as std::ops::Sub>::Output`
   = note: you might be missing a type parameter or trait bound

error[E0369]: cannot subtract `T` from `<T as std::ops::Sub>::Output`
  --> src/bin/d.rs:90:47
   |
90 |         self.data[i1][j1] - self.data[i1][j0] - self.data[i0][j1] + self.data[i0][j0]
   |         ------------------------------------- ^ ----------------- T
   |         |
   |         <T as std::ops::Sub>::Output
   |
   = note: an implementation of `std::ops::Sub` might be missing for `<T as std::ops::Sub>::Output`
```

トレイト境界に、演算子のオーバーロードに必要なstd::ops::Subを追加しましたが、まだ怒られます。
これは`T`と`T`の引き算の結果が`T`であるとは限らないことに起因します。
Rustくんは本当に細かいなぁ…

以下のように`<Output=T>`を付けたトレイト境界を定めることで、上記条件を保証することが可能です。


```Rust
impl<T> CumSum2D<T>
    where T: Zero + Copy + Clone + Sub<Output=T>
```

完成コード
===
```Rust
use cumsum2d::CumSum2D;

pub mod cumsum2d {
    use num_traits::Zero;
    use std::ops::Sub;

    #[derive(Debug, Clone)]
    pub struct CumSum2D<T> {
        pub data: Vec<Vec<T>>,
    }

    impl<T> CumSum2D<T>
        where T: Zero + Copy + Clone + Sub<Output=T>
    {
        pub fn from(input: &Vec<Vec<T>>) -> Self {
            let h = input.len();
            let w = input[0].len();
            let mut data = vec![vec![T::zero(); w + 1]; h + 1];
            for i in 1..=h {
                for j in 1..=w {
                    data[i][j] = data[i - 1][j] + data[i][j - 1] + input[i - 1][j - 1] - data[i - 1][j - 1];
                }
            }
            CumSum2D { data }
        }

        pub fn query(&self, i0: usize, i1: usize, j0: usize, j1: usize) -> T {
            self.data[i1][j1] - self.data[i1][j0] - self.data[i0][j1] + self.data[i0][j0]
        }
    }

    #[test]
    fn test_cumsum2d() {
        let cs = CumSum2D::from(&vec![vec![1, 2, 3, 4], vec![5, 6, 7, 8], vec![9, 10, 11, 12]]);
        assert_eq!(cs.query(0, 3, 0, 4), 78);
        assert_eq!(cs.query(0, 1, 0, 1), 1);
        assert_eq!(cs.query(1, 3, 1, 3), 34);

        // for i64
        let cs = CumSum2D::from(&vec![vec![1i64, 2, 3, 4], vec![5, 6, 7, 8], vec![9, 10, 11, 12]]);
        assert_eq!(cs.query(0, 3, 0, 4), 78i64);

        // for u64
        let cs = CumSum2D::from(&vec![vec![1u64, 2, 3, 4], vec![5, 6, 7, 8], vec![9, 10, 11, 12]]);
        assert_eq!(cs.query(0, 3, 0, 4), 78u64);

        // for usize
        let cs = CumSum2D::from(&vec![vec![1usize, 2, 3, 4], vec![5, 6, 7, 8], vec![9, 10, 11, 12]]);
        assert_eq!(cs.query(0, 3, 0, 4), 78usize);

        // // for f64
        // // Cargo.tomlに以下を追加してね
        // // assert_approx_eq = "1.1.0"
        // use assert_approx_eq::assert_approx_eq;
        // use num_traits::Float;
        // let cs =  CumSum2D::from(&vec![vec![0.1,0.2,0.3,0.4],
        //                                vec![0.5,0.6,0.7,0.8],
        //                                vec![0.9,1.0,1.1,1.2]]);
        // assert_approx_eq!(cs.query(1, 3, 1, 3), 3.4);
    }
}
```

最後に
===
ABC203-Dで[AC](https://atcoder.jp/contests/abc203/submissions/23123294)出たんで大丈夫かと思うんですが、実装コードに誤りがあったら教えて下さい。


参考
===

- [累積和を何も考えずに書けるようにする！](https://qiita.com/drken/items/56a6b68edef8fc605821)
- [【Rust】ジェネリクスの取説](https://qiita.com/quasardtm/items/09952838a6ee9582db1d)
- [Rust by Example 日本語版](https://doc.rust-jp.rs/rust-by-example-ja/)