Weakness of the implementation of segtree (maybe a bug?)

[cirnovsky]

The function prod(l, r) simply sets sml = e(), smr = e(), and then merges them with op(x, y).

But note that "empty value" not always equals "illegal value".

It means that, when there is an "illegal value" on left son or right son, the father node will be also filled with "illegal value", but when you do range query, sometimes the left son / right son may be empty (not included in query range). At this contition, it can't simply set initial values to e(), since e() means "illegal value" now.

E.g. when maintaining congruence equations, "has no solution" not equals to "empty value".

I didn't explain it clearly I think...But maybe you can see this code to find the problem.

Maybe add a new value to identity it or do a special check will work.

[cirnovsky]

In other word, there exists such a type of e() that $e()\cdot x=e()$ (which is different from $e()\cdot x=x$).

Funcion prod(l, r) in ACL sets left sons and right sons that are not included in query range as e() , which expects e()\cdot x=x. But if the rule is $e()\cdot x=e()$, we need to do a special check, as following.

S prod(int p, int l, int r, int x, int y) {
  if (l >= x && r <= y) return t[p];
  int mid = (l + r) >> 1;
  S res = e();
  if (mid >= x) res = prod(lc(p), l, mid, x, y);
  if (mid < y) {
    if (mid >= x)
      res = op(res, prod(rc(p), mid + 1, r, x, y));
    else
      res = prod(rc(p), mid + 1, r, x, y);
  }
  return res;
}

With the way to code above, $e()\cdot x=x$ could also work.

[cirnovsky]

[yosupo06]

Yes, ACL assume the existence of identity element e(), e() * x = x. (In mathematical, ACL can handle Monoid, not Semigroup).

When you want to use type T which doesn't have identity element e(), you can use pair<T, bool> as follows:

T op(T a, T b) { return something; }

pair<T, bool> e() {
  return {some_dummy_value, false};
}

pair<T, bool> op2(pair<T, bool> a, pair<T, bool> b) {
  if (!a.second || !b.second) return {some_dummy_value, false};
  return {op(a, b), true};
}

[cirnovsky]

Yes, ACL assume the existence of identity element e(), e() * x = x. (In mathematical, ACL can handle Monoid, not Semigroup).

When you want to use type T which doesn't have identity element e(), you can use pair<T, bool> as follows:

T op(T a, T b) { return something; }

pair<T, bool> e() {
  return {some_dummy_value, false};
}

pair<T, bool> op2(pair<T, bool> a, pair<T, bool> b) {
  if (!a.second || !b.second) return {some_dummy_value, false};
  return {op(a, b), true};
}

oh yes, it also works.

thanks for replying.