Declaring several methods in atcoder::segtree as const

[hitonanode]

I want to append const to several method declarations in atcoder::segtree.

Some complicated DP problems require to maintain two segtrees to improve time complexity. In such situations, coders always have to pay attention to them. If one of them is not modifed at all (used like (disjoint) sparse tables), I want to declare it as const to reduce the risk of updating the wrong segtree.

In current ACL, all atcoder::segtree methods are not declared as const, so we cannot declare the instances as const when there is no update query. On the other hand, it seems that the methods get(), prod(), all_prod(), max_right() and min_left() do not affect any member variables. I suggest that these methods have const like this to enable such usage of atcoder::segtree.

What do you think of this modification?

[yosupo06]

The situation that your suggested makes sense for me.

Otherhand, we have a concern about your modification: If segtree.prod() is const whereas lazysegtree.prod() isn't const, it may be confusing.

Probably we can solve this problem by mutable or const_cast or something, but I haven't checked yet.

[hitonanode]

Thanks for comments, @yosupo06. I understood the concern on the consistency of interface, and tried writing const-friendly lazy_segtrees. I first wrote the one using mutable , which is simple but might be accused of abusing mutable. I then wrote another one using const_cast, which perhaps requires a little knowledge of pointers to readers. What type of modification (or do nothing) is more preferable for ACL (Lazy) Segtrees?

Below are the lazy_segtree submissions for some problems on OJs. Though it may be obvious, it seems that no constant factor degradation is observed because of these modifications.

Problem	Used methods	Plain lazy_segtree	mutable	const_cast
AC practice2-K	prod(), apply()	GCC, 866 ms / Clang, 927 ms	GCC, 835 ms / Clang, 797 ms	GCC, 881 ms / Clang, 861 ms
AC practice2-L	prod(), apply()	GCC, 265 ms / Clang, 231 ms	GCC, 267 ms / Clang, 234 ms	GCC, 263 ms / Clang, 239 ms
AC ACLBC-E	prod(), apply()	GCC, 252 ms / Clang, 245 ms	GCC, 245 ms / Clang, 238 ms	GCC, 246 ms / Clang, 239 ms
CF 555C	get(), apply()	GNU C++17 (64), 592 ms	GNU C++17 (64), 576 ms	GNU C++17 (64), 577 ms
TOKI troc17F	apply(), max_right()	C++17, 138 ms	C++17, 141 ms	C++17, 145 ms

[yosupo06]

Thanks for your careful investigation. I feel mutable is better.