So here is the thing: recently I was doing some sustainable data structure problems while I found that the behavior of vector seems to vary from C++ standard versions. I did a little experiment:

#include <vector>
#include <cstdio>
using namespace std;
const int MAXN = 1000006;

int n;
int arr[MAXN];

struct SegTreeNode
{
    SegTreeNode(int _l = 0, int _r = 0, int _v = 0)
    {
        val = _v;
        ls = rs = -1;
        sl = _l, sr = _r;
    }
    int val;
    int ls, rs;
    int sl, sr;
};

vector<SegTreeNode> sgt;
int root;

inline int newNode(int sl, int sr, int val)
{
    sgt.push_back(SegTreeNode(sl, sr, val));
    return sgt.size() - 1;
}
int build(int l, int r)
{
    int t = newNode(l, r, 0);
    if (l == r)
    {
        sgt[t].val = arr[l];
        return t;
    }
    int mid = (l + r) >> 1;
    sgt[t].ls = build(l, mid);
    sgt[t].rs = build(mid + 1, r);
    sgt[t].val = sgt[sgt[t].ls].val + sgt[sgt[t].rs].val;
    return t;
}
int query(int idx, int l, int r)
{
    if (l <= sgt[idx].sl && sgt[idx].sr <= r)
        return sgt[idx].val;
    int mid = (sgt[idx].sl + sgt[idx].sr) >> 1;
    int res = 0;
    if (l <= mid)
        res += query(sgt[idx].ls, l, r);
    if (r > mid)
        res += query(sgt[idx].rs, l, r);
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", arr + i);
    root = build(1, n);
    int l, r;
    scanf("%d %d", &l, &r);
    printf("%d\n", query(root, l, r));
    for (int i = 1; i <= n; i++)
        printf("%d ", query(root, i, i));
    printf("\n");
    for (SegTreeNode nd : sgt)
        printf("val=%d [%d,%d] ls=%d rs=%d\n", nd.val, nd.sl, nd.sr, nd.ls, nd.rs);
    return 0;
}

It's just a basic segment tree with dynamically allocated nodes. I compiled the same code in both C++14 and C++17, and I got different output from two programs:

Input:
5
1 2 3 4 5
1 4

C++14:
8
4 4 4 4 4
val=8 [1,5] ls=-1 rs=-1
val=4 [1,3] ls=-1 rs=5
val=2 [1,2] ls=3 rs=-1
val=1 [1,1] ls=-1 rs=-1
val=2 [2,2] ls=-1 rs=-1
val=3 [3,3] ls=-1 rs=-1
val=8 [4,5] ls=7 rs=-1
val=4 [4,4] ls=-1 rs=-1
val=5 [5,5] ls=-1 rs=-1

C++17:
10
1 2 3 4 5
val=15 [1,5] ls=1 rs=6
val=6 [1,3] ls=2 rs=5
val=3 [1,2] ls=3 rs=4
val=1 [1,1] ls=-1 rs=-1
val=2 [2,2] ls=-1 rs=-1
val=3 [3,3] ls=-1 rs=-1
val=9 [4,5] ls=7 rs=8
val=4 [4,4] ls=-1 rs=-1
val=5 [5,5] ls=-1 rs=-1

Only the result of C++17 is correct. I also modified the program to use static arrays and the correct output appears in both C++14 and C++17. So I'm confident that the vector in C++14 is to blame.

Can anyone explain why it happens? I tried to compile the source into assembly code and I did found that there are differences, but I can't understand them: dynamic-segtree-cpp14.asm, dynamic-segtree-cpp17.asm. Do they provide clearer evidence?

I came up with them all when I was in a daze during classes in school.

This post is a practice translation for helping myself get familiar to English math terms. So if I made any mistakes, it will be grateful if you could correct them in the comments. Original post (Chinese) is here: https://www.luogu.com.cn/blog/andycode3759/math-proofs

Proposition 1

Proposition: Convex n-polygon $$$(n \geq 4)$$$ has $$${{n(n-3)} \over 2}$$$ diagonals.

Proof: Draw a convex n-polygon in a plane randomly and we can get its $$$n$$$ vertices, among which we can connect any two of them to get $$$C_{n}^{2}$$$ line segments in total, in which $$$n$$$ of them are the edges of the polygon, and the rest $$$C_{n}^{2}-n={{n(n-3)} \over 2}$$$ of them are the diagonals. Proved in only one sentence!

Proposition 2

Proposition: There are two independent (thanks nor for correcting it) finite discrete random variables $$$X$$$ and $$$Y$$$ whose expectations are $$$E(X)$$$ and $$$E(Y)$$$ and variances are $$$D(X)$$$ and $$$D(Y)$$$. Then $$$E(X+Y)=E(X)+E(Y), D(X+Y)=D(X)+D(Y)$$$.

Proof:

(i) Assume the distributions of $$$X$$$ and $$$Y$$$ are $$$P(X=x_i)=p_i(1 \leq i \leq n),P(Y=y_i)=q_i(1 \leq i \leq m)$$$, then

Obviously we have

So

(ii) For convenience, take $$$dx_i$$$ as $$$x_i-E(X)$$$ and $$$dy_i$$$ as $$$y_i-E(Y)$$$. First we need a lemma:

(Also apply to $$$Y$$$.) The proof is simple:

Since we have

Then

Q.E.D.

Proposition 3

Proposition: $$$\forall n \in \mathbb{N}^{+}, 1^2+2^2+3^2+ \dots +n^2 = \sum_{k=1}^{n}k^2 = {1 \over 6}n(n+1)(2n+1)$$$ (The sum of squares of the first $$$n$$$ positive integers).

Proof: It is noticed that:

We can write $$$n$$$ equations like these and add them up, then the left side is $$$1^2+2^2+\dots+n^2$$$, and the right side is the sum of $$$n$$$ times $$$1$$$, $$$(n-1)$$$ times $$$3$$$, ..., $$$(n-k+1)$$$ times $$$(2k-1)$$$, ..., $$$1$$$ times $$$(2n-1)$$$. So we will get

Reduce the right side of the equation:

Do the transposition:

Q.E.D.