Implement segment tree

[Luzhiled]

概要 / Overview

遅延セグメント木と双対セグメント木を実装しました

いくつかの典型的なものについてはあらかじめモノイドを用意しておきました (全13種)

関連 issue, PR / Related issues, PRs

• 87

• 86

TODO

Segment Tree 共通ドキュメント

• [x] ドキュメントの更新

Segment Tree

• [x] ドキュメントの update

Lazy Segment Tree

• [x] 実装
• [x] ドキュメント作成
• [x] verify

Dual Segment Tree

• [x] 実装
• [x] ドキュメント作成
• [x] verify

preset

• [x] Range Minimum Query
  • [x] 実装
  • [x] ドキュメント作成
  • [x] verify (DSL_2_A)
• [x] Range Maximum Query
  • [x] 実装
  • [x] ドキュメント作成
  • [x] verify (abc298_f)
• [x] Range Sum Query
  • [x] 実装
  • [x] ドキュメント作成
  • [x] verify (DSL_2_B)
• [x] Range Update Query
  • [x] 実装
  • [x] ドキュメント作成
  • [x] verify (DSL_2_D)
• [x] Range Add Query
  • [x] 実装
  • [x] ドキュメント作成
  • [x] verify (DSL_2_E)
• [x] Range chmin Query
  • [x] 実装
  • [x] ドキュメント作成
  • [x] verify (abc179_f)
• [x] Range chmax Query
  • [x] 実装
  • [x] ドキュメント作成
  • [x] verify (abc179_f 符号反転)
• [x] Range Update Range Minimum Query
  • [x] 実装
  • [x] ドキュメント作成
  • [x] verify (DSL_2_F)
• [x] Range Add Range Minimum Query
  • [x] 実装
  • [x] ドキュメント作成
  • [x] verify (DSL_2_H)
• [x] Range Update Range Maximum Query
  • [x] 実装
  • [x] ドキュメント作成
  • [x] verify (DSL_2_F 符号反転)
• [x] Range Add Range Maximum Query
  • [x] 実装
  • [x] ドキュメント作成
  • [x] verify (DSL_2_H 符号反転)
• [x] Range Update Range Sum Query
  • [x] 実装
  • [x] ドキュメント作成
  • [x] verify (DSL_2_I)
• [x] Range Add Range Sum Query
  • [x] 実装
  • [x] ドキュメント作成
  • [x] verify (DSL_2_G)

CI 関連項目

verify-check / verify

(cd $(git rev-parse --show-toplevel) && oj-verify all)

clang-format

(cd $(git rev-parse --show-toplevel) && clang-format -i $(find src/ test/ unit-test/ -name "*.hpp" -or -name "*.cpp"))

[Luzhiled]

CI がすげえ重くなりそうだし workflow を先にいじってしまいます

[ei1333]

まちがえた

[Luzhiled]

ちゃんと手動で実行する形式にできていそうですね

verify をしたいときは https://github.com/luzhiled1333/comp-library/actions/workflows/verify-check.yml から Run workflow を押してブランチを指定してえいすると動きます

[Luzhiled]

✅Draft PR に approve をつけない

[Luzhiled]

今のところ Dual はバグってなさそうですね　OK

[Luzhiled]

chmin / chmax も追加しようかなって

[Luzhiled]

range chmax の問題どっかにないかな

[Luzhiled]

すいません　clang-format が

[Luzhiled]

まあ Lazy Segment Tree のほうも盛大にバグってはなさそうだな

[Luzhiled]

clang-format やってないってワケ

[Luzhiled]

バグっているのを見なかったことにすると全部実装自体はできましたね

[Luzhiled]

今日も元気にclang-formatを忘れて落ちる

[Luzhiled]

presets/ 下のものもすべて実装してドキュメントも書きました

min のほうとやっていること何も変わらないのでバグってはいないとは思うんだが、全体的に max クエリが必要になる問題が不足していて困っている

[Luzhiled]

ABC298-F がそういえば Range Max Query でしたね

[Luzhiled]

max 系が全然見つからなかったのであきらめて符号反転した状態で解いた

[Luzhiled]

unit test は、いいかな…………

[ei1333]

File changed 60ってなーんだ？

[Luzhiled]

https://github.com/luzhiled1333/comp-library/actions/runs/4857366862

[Luzhiled]

6分で終わるのか、けっこう早いんだな

[ei1333]

ひかりさん、その作業僕がもうやりました

[Luzhiled]

すいません、この Approve というのは merge してもいいよという意味の Approve でしょうか

[Luzhiled]

verify-check を走らせました2 https://github.com/luzhiled1333/comp-library/actions/runs/4857891437

[ei1333]

よくわからんけどマージしてもいいか

[Luzhiled]

すいません　verify-check 落ちてます

[Luzhiled]

確認してよかった

[ei1333]

Error: 429 Client Error: Too Many Requests for url:

[Luzhiled]

dropbox　カス

[Luzhiled]

まあ時間をおいて merge するか　今までありがとう

[ei1333]

すみません　verify-check落ちてますよ

[Luzhiled]

https://help.dropbox.com/ja-jp/share/banned-links 24時間！！？！？？

[ei1333]

ん、これマージをしてもよいですか？

[Luzhiled]

24時間経ったので merge してしまいます