Fenwick range update

    class Tree {
        long[] dataMul;
        long[] dataAdd;

        Tree(int n) {
            dataMul = new long[n + 1];
            dataAdd = new long[n + 1];
        }

        void update(int left, int right, long by) {
            internalUpdate(left, by, -by * (left - 1));
            internalUpdate(right, -by, by * right);
        }

        void internalUpdate(int at, long mul, long add) {
            for (at++; at < dataMul.length; at += at & -at) {
                dataMul[at] += mul;
                dataAdd[at] += add;
            }
        }

        long query(int at) {
            long mul = 0;
            long add = 0;
            int start = at;
            for (at++; at > 0; at -= at & -at) {
                mul += dataMul[at];
                add += dataAdd[at];
            }
            return mul * start + add;
        }

        long query(int left, int right) {
            return query(right) - query(left - 1);
        }
    }