With **Atcoder API** of **Lazy Segment Tree,** [Lazy Seg Tree Template](https://github.com/atcoder/ac-library/blob/master/atcoder/lazysegtree.hpp) <br> I am trying the problem where we need to support query to increment a range with a given value.↵
↵
The Atcoder API implementation seems to fail here, where I have an array.↵
<br>↵
↵
**[3, 2, 4, 5, 1, 1, 5, 3]**↵
<br>↵
↵
↵
and I want to do a range update over the range **[1,4] ( 0 based indexing)** and **add a value 1** to it.↵
<br>↵
The sum should ideally change to **16** after the update and the **array** should look like <br>↵
↵
**[3, 3, 5, 6, 2, 1, 5, 3]**↵
<br>↵
↵
↵
The query function , the **.prod()** function of Atcoder API seems to return result **15**,<br> You can try running this code for your reference to understand the ambiguity happening here.↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include<bits/stdc++.h>↵
namespace internal {↵
unsigned int bit_ceil(unsigned int n) {↵
unsigned int x = 1;↵
while (x < (unsigned int)(n)) x *= 2;↵
return x;↵
}↵
int countr_zero(unsigned int n) {↵
#ifdef _MSC_VER↵
unsigned long index;↵
_BitScanForward(&index, n);↵
return index;↵
#else↵
return __builtin_ctz(n);↵
#endif↵
}↵
constexpr int countr_zero_constexpr(unsigned int n) {↵
int x = 0;↵
while (!(n & (1 << x))) x++;↵
return x;↵
}↵
}↵
template <class S,↵
S (*op)(S, S),↵
S (*e)(),↵
class F,↵
S (*mapping)(F, S),↵
F (*composition)(F, F),↵
F (*id)()>↵
struct lazy_segtree {↵
↵
public:↵
lazy_segtree() : lazy_segtree(0) {}↵
explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}↵
explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {↵
size = (int)internal::bit_ceil((unsigned int)(_n));↵
log = internal::countr_zero((unsigned int)size);↵
d = std::vector<S>(2 * size, e());↵
lz = std::vector<F>(size, id());↵
for (int i = 0; i < _n; i++) d[size + i] = v[i];↵
for (int i = size - 1; i >= 1; i--) {↵
update(i);↵
}↵
}↵
↵
void set(int p, S x) {↵
assert(0 <= p && p < _n);↵
p += size;↵
for (int i = log; i >= 1; i--) push(p >> i);↵
d[p] = x;↵
for (int i = 1; i <= log; i++) update(p >> i);↵
}↵
↵
S get(int p) {↵
assert(0 <= p && p < _n);↵
p += size;↵
for (int i = log; i >= 1; i--) push(p >> i);↵
return d[p];↵
}↵
↵
S prod(int l, int r) {↵
assert(0 <= l && l <= r && r <= _n);↵
if (l == r) return e();↵
↵
l += size;↵
r += size;↵
↵
for (int i = log; i >= 1; i--) {↵
if (((l >> i) << i) != l) push(l >> i);↵
if (((r >> i) << i) != r) push((r - 1) >> i);↵
}↵
↵
S sml = e(), smr = e();↵
while (l < r) {↵
if (l & 1) sml = op(sml, d[l++]);↵
if (r & 1) smr = op(d[--r], smr);↵
l >>= 1;↵
r >>= 1;↵
}↵
↵
return op(sml, smr);↵
}↵
↵
S all_prod() { return d[1]; }↵
↵
void apply(int p, F f) {↵
assert(0 <= p && p < _n);↵
p += size;↵
for (int i = log; i >= 1; i--) push(p >> i);↵
d[p] = mapping(f, d[p]);↵
for (int i = 1; i <= log; i++) update(p >> i);↵
}↵
void apply(int l, int r, F f) {↵
assert(0 <= l && l <= r && r <= _n);↵
if (l == r) return;↵
↵
l += size;↵
r += size;↵
↵
for (int i = log; i >= 1; i--) {↵
if (((l >> i) << i) != l) push(l >> i);↵
if (((r >> i) << i) != r) push((r - 1) >> i);↵
}↵
↵
{↵
int l2 = l, r2 = r;↵
while (l < r) {↵
if (l & 1) all_apply(l++, f);↵
if (r & 1) all_apply(--r, f);↵
l >>= 1;↵
r >>= 1;↵
}↵
l = l2;↵
r = r2;↵
}↵
↵
for (int i = 1; i <= log; i++) {↵
if (((l >> i) << i) != l) update(l >> i);↵
if (((r >> i) << i) != r) update((r - 1) >> i);↵
}↵
}↵
private:↵
int _n, size, log;↵
std::vector<S> d;↵
std::vector<F> lz;↵
↵
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }↵
void all_apply(int k, F f) {↵
d[k] = mapping(f, d[k]);↵
if (k < size) lz[k] = composition(f, lz[k]);↵
}↵
void push(int k) {↵
all_apply(2 * k, lz[k]);↵
all_apply(2 * k + 1, lz[k]);↵
lz[k] = id();↵
}↵
};↵
int64_t add(int64_t a,int64_t b){↵
return a+b;↵
}↵
int64_t e(){↵
return 0;↵
}↵
struct F{↵
int64_t x;↵
};↵
int64_t mapping(F f,int64_t s){↵
return f.x+s;↵
}↵
F composition(F a,F b){↵
return F{a.x+b.x};↵
}↵
F id(){↵
return F{(int64_t)0};↵
}↵
signed main(){ ↵
uint32_t N = 8;↵
std::vector<int64_t> arr = {3, 2 ,4 ,5 ,1 ,1 ,5 ,3};↵
lazy_segtree<int64_t,add,e,F,mapping,composition,id> tree(arr);↵
tree.apply(1,5,F{1});↵
for(uint32_t i=0;i<N;i++){↵
std::cout << tree.get(i) << " ";↵
}↵
std::cout <<"\n";↵
std::cout << tree.prod(1,5) << "\n";↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Output">↵
3 3 5 6 2 1 5 3<br>↵
15↵
</spoiler>↵
↵
<br>↵
I am using CPP20 and I am pretty sure (almost 99%) that it is a bug in their implementation,<br> just want someone to acknowledge it or maybe tell what am I missing here. <br> ↵
cc [user:yosupo,2023-05-02] <br>↵
↵
UPD -> It is resolved but yeah things are kinda confusing with this template. ↵
↵
UPD 2-> This template is quite useful if you ever gone through the Polynomial queries question in CSES section about adding AP to a range . It is one among the toughest ones.↵
↵
Here is the complete structure to AC it using AtCoder Template.↵
↵
<spoiler summary="Polynomial Queries CSES">↵
↵
~~~~~↵
struct S{↵
int64_t value,size,index;↵
};↵
S op(S a,S b){↵
return S{a.value + b.value,a.size + b.size,a.index}; ↵
}↵
S id(){↵
return S{0,0,-1};↵
}↵
struct F{↵
int64_t ap,cd,index; ↵
};↵
S mapping(F f, S s){↵
int64_t value = s.value;↵
int64_t size = s.size;↵
int64_t j = s.index;↵
int64_t i = f.index;↵
int64_t ap = f.ap;↵
int64_t cd = f.cd;↵
int64_t first_term = ap + (j-i)*cd;↵
int64_t sum = ((size)*(2*first_term + (size-1)*cd))/2;↵
return S{value + sum ,size,j};↵
}↵
F composition(F f,F g){↵
if(f.index > g.index){↵
std::swap(f,g);↵
}↵
int64_t Aleft = f.ap;↵
int64_t Aright = g.ap;↵
int64_t posLeft = f.index;↵
int64_t posRight = g.index;↵
int64_t cdLeft = f.cd;↵
int64_t cdRight = g.cd;↵
int64_t finalA = Aleft + (posRight-posLeft)*cdLeft + Aright;↵
int64_t finalcd = cdLeft + cdRight;↵
return F{finalA,finalcd,posRight}; ↵
}↵
F e(){↵
return F{0,0,0};↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
↵
The Atcoder API implementation seems to fail here, where I have an array.↵
<br>↵
↵
**[3, 2, 4, 5, 1, 1, 5, 3]**↵
<br>↵
↵
↵
and I want to do a range update over the range **[1,4] ( 0 based indexing)** and **add a value 1** to it.↵
<br>↵
The sum should ideally change to **16** after the update and the **array** should look like <br>↵
↵
**[3, 3, 5, 6, 2, 1, 5, 3]**↵
<br>↵
↵
↵
The query function , the **.prod()** function of Atcoder API seems to return result **15**,<br> You can try running this code for your reference to understand the ambiguity happening here.↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include<bits/stdc++.h>↵
namespace internal {↵
unsigned int bit_ceil(unsigned int n) {↵
unsigned int x = 1;↵
while (x < (unsigned int)(n)) x *= 2;↵
return x;↵
}↵
int countr_zero(unsigned int n) {↵
#ifdef _MSC_VER↵
unsigned long index;↵
_BitScanForward(&index, n);↵
return index;↵
#else↵
return __builtin_ctz(n);↵
#endif↵
}↵
constexpr int countr_zero_constexpr(unsigned int n) {↵
int x = 0;↵
while (!(n & (1 << x))) x++;↵
return x;↵
}↵
}↵
template <class S,↵
S (*op)(S, S),↵
S (*e)(),↵
class F,↵
S (*mapping)(F, S),↵
F (*composition)(F, F),↵
F (*id)()>↵
struct lazy_segtree {↵
↵
public:↵
lazy_segtree() : lazy_segtree(0) {}↵
explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}↵
explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {↵
size = (int)internal::bit_ceil((unsigned int)(_n));↵
log = internal::countr_zero((unsigned int)size);↵
d = std::vector<S>(2 * size, e());↵
lz = std::vector<F>(size, id());↵
for (int i = 0; i < _n; i++) d[size + i] = v[i];↵
for (int i = size - 1; i >= 1; i--) {↵
update(i);↵
}↵
}↵
↵
void set(int p, S x) {↵
assert(0 <= p && p < _n);↵
p += size;↵
for (int i = log; i >= 1; i--) push(p >> i);↵
d[p] = x;↵
for (int i = 1; i <= log; i++) update(p >> i);↵
}↵
↵
S get(int p) {↵
assert(0 <= p && p < _n);↵
p += size;↵
for (int i = log; i >= 1; i--) push(p >> i);↵
return d[p];↵
}↵
↵
S prod(int l, int r) {↵
assert(0 <= l && l <= r && r <= _n);↵
if (l == r) return e();↵
↵
l += size;↵
r += size;↵
↵
for (int i = log; i >= 1; i--) {↵
if (((l >> i) << i) != l) push(l >> i);↵
if (((r >> i) << i) != r) push((r - 1) >> i);↵
}↵
↵
S sml = e(), smr = e();↵
while (l < r) {↵
if (l & 1) sml = op(sml, d[l++]);↵
if (r & 1) smr = op(d[--r], smr);↵
l >>= 1;↵
r >>= 1;↵
}↵
↵
return op(sml, smr);↵
}↵
↵
S all_prod() { return d[1]; }↵
↵
void apply(int p, F f) {↵
assert(0 <= p && p < _n);↵
p += size;↵
for (int i = log; i >= 1; i--) push(p >> i);↵
d[p] = mapping(f, d[p]);↵
for (int i = 1; i <= log; i++) update(p >> i);↵
}↵
void apply(int l, int r, F f) {↵
assert(0 <= l && l <= r && r <= _n);↵
if (l == r) return;↵
↵
l += size;↵
r += size;↵
↵
for (int i = log; i >= 1; i--) {↵
if (((l >> i) << i) != l) push(l >> i);↵
if (((r >> i) << i) != r) push((r - 1) >> i);↵
}↵
↵
{↵
int l2 = l, r2 = r;↵
while (l < r) {↵
if (l & 1) all_apply(l++, f);↵
if (r & 1) all_apply(--r, f);↵
l >>= 1;↵
r >>= 1;↵
}↵
l = l2;↵
r = r2;↵
}↵
↵
for (int i = 1; i <= log; i++) {↵
if (((l >> i) << i) != l) update(l >> i);↵
if (((r >> i) << i) != r) update((r - 1) >> i);↵
}↵
}↵
private:↵
int _n, size, log;↵
std::vector<S> d;↵
std::vector<F> lz;↵
↵
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }↵
void all_apply(int k, F f) {↵
d[k] = mapping(f, d[k]);↵
if (k < size) lz[k] = composition(f, lz[k]);↵
}↵
void push(int k) {↵
all_apply(2 * k, lz[k]);↵
all_apply(2 * k + 1, lz[k]);↵
lz[k] = id();↵
}↵
};↵
int64_t add(int64_t a,int64_t b){↵
return a+b;↵
}↵
int64_t e(){↵
return 0;↵
}↵
struct F{↵
int64_t x;↵
};↵
int64_t mapping(F f,int64_t s){↵
return f.x+s;↵
}↵
F composition(F a,F b){↵
return F{a.x+b.x};↵
}↵
F id(){↵
return F{(int64_t)0};↵
}↵
signed main(){ ↵
uint32_t N = 8;↵
std::vector<int64_t> arr = {3, 2 ,4 ,5 ,1 ,1 ,5 ,3};↵
lazy_segtree<int64_t,add,e,F,mapping,composition,id> tree(arr);↵
tree.apply(1,5,F{1});↵
for(uint32_t i=0;i<N;i++){↵
std::cout << tree.get(i) << " ";↵
}↵
std::cout <<"\n";↵
std::cout << tree.prod(1,5) << "\n";↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Output">↵
3 3 5 6 2 1 5 3<br>↵
15↵
</spoiler>↵
↵
<br>↵
I am using CPP20 and I am pretty sure (almost 99%) that it is a bug in their implementation,<br> just want someone to acknowledge it or maybe tell what am I missing here. <br> ↵
cc [user:yosupo,2023-05-02] <br>↵
↵
UPD -> It is resolved but yeah things are kinda confusing with this template. ↵
↵
UPD 2-> This template is quite useful if you ever gone through the Polynomial queries question in CSES section about adding AP to a range . It is one among the toughest ones.↵
↵
Here is the complete structure to AC it using AtCoder Template.↵
↵
<spoiler summary="Polynomial Queries CSES">↵
↵
~~~~~↵
struct S{↵
int64_t value,size,index;↵
};↵
S op(S a,S b){↵
return S{a.value + b.value,a.size + b.size,a.index}; ↵
}↵
S id(){↵
return S{0,0,-1};↵
}↵
struct F{↵
int64_t ap,cd,index; ↵
};↵
S mapping(F f, S s){↵
int64_t value = s.value;↵
int64_t size = s.size;↵
int64_t j = s.index;↵
int64_t i = f.index;↵
int64_t ap = f.ap;↵
int64_t cd = f.cd;↵
int64_t first_term = ap + (j-i)*cd;↵
int64_t sum = ((size)*(2*first_term + (size-1)*cd))/2;↵
return S{value + sum ,size,j};↵
}↵
F composition(F f,F g){↵
if(f.index > g.index){↵
std::swap(f,g);↵
}↵
int64_t Aleft = f.ap;↵
int64_t Aright = g.ap;↵
int64_t posLeft = f.index;↵
int64_t posRight = g.index;↵
int64_t cdLeft = f.cd;↵
int64_t cdRight = g.cd;↵
int64_t finalA = Aleft + (posRight-posLeft)*cdLeft + Aright;↵
int64_t finalcd = cdLeft + cdRight;↵
return F{finalA,finalcd,posRight}; ↵
}↵
F e(){↵
return F{0,0,0};↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
