C++ segment tree solution - different then everybody else's but just as fast
\nclass Solution {\npublic:\n    /*\n     * Tha matrix is represented as a n_rows * n_cols\n     * segment tree.\n     */\n    struct Seg {\n        int n; // n
```\nclass Solution {\npublic:\n    /*\n     * Tha matrix is represented as a n_rows * n_cols\n     * segment tree.\n     */\n    struct Seg {\n        int n; // number of points in this subtree\n        int a; // for leaves, a starting point of this interval\n        Seg *left, *right;\n    };\n    int n_rows, n_cols;\n    Seg root;\n    \n    Solution(int a_n_rows, int a_n_cols) {\n        n_rows = a_n_rows;\n        n_cols = a_n_cols;\n        root = { n_rows * n_cols, 0, 0, 0 };\n    }\n    \n    vector<int> flip() {\n        int r = random() % root.n;\n        \n        // find r-th point in the tree\n        Seg *s = &root;\n        while (s->left || s->right) {\n            if (s->left && r < s->left->n) {\n                --s->n;\n                s = s->left;\n            } else if (s->right) {\n                --s->n;\n                r -= s->left->n;\n                s = s->right;\n            }\n        }\n        \n        // get the result\n        int a = s->a + r;\n        \n        // update the tree - split the leaf-level interval\n        --s->n;\n        if (a == s->a) {\n            ++s->a;\n        } else if (a == s->a + s->n) {\n            /* nothing else to do */\n        } else {\n            s->left = new Seg;\n            s->left->a = s->a;\n            s->left->n = r;\n            s->left->left = s->left->right = 0;\n            \n            s->right = new Seg;\n            s->right->a = s->a + r + 1;\n            s->right->n = s->n - r;\n            s->right->left = s->right->right = 0;\n        }\n        \n        return { a / n_cols, a % n_cols };\n    }\n    \n    void rec_del(Seg *s) {\n        if (s->left)\n            rec_del(s->left);\n        if (s->right)\n            rec_del(s->right);\n        delete s;\n    }\n    \n    void reset() {\n        if (root.left)\n            rec_del(root.left);\n        if (root.right)\n            rec_del(root.right);\n        root = { n_rows * n_cols, 0, 0, 0 };\n    }\n};\n```
[]