Class: binary_indexed_tree

Simplified | 简体中文版

最基本的树状数组。支持单点修改和区间询问。

定义：template<int _N, class _Val_t, class _Op> class binary_indexed_tree

• int _N：区间大小；
• class _Val_t：存储数据类型；
• class _Op：支持的运算。（树状数组支持满足结合律的运算）

类型

binary_indexed_tree<_N, _Val_t, _Op>::value_type：存储类型（aka. _Val_t）；

binary_indexed_tree<_N, _Val_t, _Op>::operate_type：运算类型（aka. _Op）。

成员函数

binary_indexed_tree<_N, _Val_t, _Op>::binary_indexed_tree(value_type identity)（构造函数）

可以构造一个元素均为 identity 初始的树状数组。

• value_type identity：即单位元。

binary_indexed_tree<_N, _Val_t, _Op>::modify(int ptr, value_type val)

进行单点修改，在 ptr 的位置上 加上 val。

• int ptr：位置指针（从 0 开始）；
• value_type val：修改值。

binary_indexed_tree<_N, _Val_t, _Op>::query(int qr)

区间询问 [0,qr] 的值的 和。

• int qr：位置指针（从 0 开始）。