i += i & -i; この動作がわからないです。

Question

教えていただきたいこと

以下のソースのadd関数とgetSum関数にある**i += i & -i;この１文のi**の動きがわからないです。

該当のソースコード

#include <bits/stdc++.h>

using namespace std;

const int N = 100000 ;
int size, c, L[N], R[N], tree[2*N+1];
vector<int> vec[N];

void init(int v) {
    L[v] = ++c;
    for (int i = 0; i < vec[v].size(); i++) {
        init(vec[v][i]);
    }
    R[v] = ++c;
}

void add(int i,int x) {
    while (i <= size) {
        tree[i] += x;
        i += i & -i;
    }
}

int getSum(int i) {
    int ans = 0;
    while (i > 0) {
        ans += tree[i];
        i -= i & -i;
    }
    return ans;
}

void query(int i) {
    if (i == 0) {
        int v, w;
        cin >> v >> w;
        add(L[v], w);
        add(R[v], -w);
    } else {
        int v;
        cin >> v;
        cout << getSum(R[v] - 1) << endl;
    }
}

int main() {
    int n;
    cin >> n;
    c = 0;
    size = 2 * n + 1;

    for (int i = 0; i < n; i++) {  // input node //
        int k;
        cin >> k;
        for (int j = 0; j < k; j++) {
            int child;
            cin >> child;
            vec[i].push_back(child);
        }
    }

    init(0);

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) { // input query //
        int op;
        cin >> op;
        query(op);
    }

    return 0;
}

Comments

[Zuishin]

https://atcoder.jp/contests/abc128/tasks/abc128_e

これですよね？
そのソースは誰のものですか？
ちゃんとリンクしてください。

[退会済みユーザー]

申し訳ありませんがそちらではございません。
よろしければリンクする必要性をお教えください。

[Zuishin]

義務です。著作権について調べてください。

[BeatStar]

リンクする必要ですか?
それは、『問題文を出さずに答えだけ出されても意味不明である』です。

たとえば、仕様的に間違っていることもあります。
プログラムは書かれた通りにしか動きません。

そもそも、プログラムは『こう書けばいい』っていうものじゃないのです。

なので、『ソースを提示しろ』と言われているのでは?

[退会済みユーザー]

今回載せているソースコードは部分的に参考にしていますが、おおよそ自分で書いたものになります。質問している2つの関数について著作権が発生するのであればそれに準じた行いをすべきだと思いますが今回は必要がないと判断させていただきました。

リンクを貼れとのことでしたが、貼ったらいい、貼ることが義務といったものは見受けられませんでした。

また、beatstarさんの仰っている問題を載せろとのことですが、上記の部分の動きのみを知りたかったのでかえって知りたいことの阻害になると思い載せませんでした。

[Zuishin]

著作権を調べたら「引用」の定義もすぐ見つかるはずなので。

[BeatStar]

あー、別に『必ず載せろ』という意味で書いたのではなく、『他の方の仰っている意味』を書いただけです。

>> また、beatstarさんの仰っている問題を載せろとのことですが

必ず載せるべきと言うわけではなく、『ソースコードだけでは何がしたいのかが不明瞭な場合がある』ため、上記でそう書いたんです。

回答者からすると、場合によっては『情報の後出し』感が半端ないこともあります。
なので上記のような書き方になりました。

[退会済みユーザー]

参考のため伺いたいのですが、今回のケースは問題がわからないと回答は困難、難解になると思いますか？

[BeatStar]

今回の場合はそこまで重要というほどでないですが、時折、仕様によることもあるので。

たとえば、他の質問者さんのものであったのですが、『わかっていない部分と質問文がかい離している』のがありました。
(トラブルのもとになりそうなので伏せますが)

そういう風に、『場合による』こともあるので、今回、私は彼/彼女の仰っていることをもうちょっと踏み込んで書いただけです。

[退会済みユーザー]

ありがとうございます。

[Zuishin]

自分で書いたものの意味を尋ねる質問をする人はいないでしょう。

他人の書いたものは他人の著作物で、それを複製することは他人の権利を侵害する不法行為であり、犯罪です。
引用の場合はそれにあたりませんが、厳格なルールがあり、出典を示すというのは引用の要件を満たすために必要な要素の一つです。

出典を示さずソースコードを複製することは犯罪です。
回答者のためではなく、著作権者と自分のために必ず載せなければいけません。

[退会済みユーザー]

例えばですがある1文をコピーした際、著作権侵害を問われることはないと考えます。今回の件、1部を参考にさせていただきましたがその部分に関しては汎用性の高さから重要度が低いと考えられます。

今回の質問は当人からの削除依頼を受け取り次第、削除させていただきます。

[Zuishin]

問われることがあるかないか調べたらすぐわかることなので調べたらいいでしょう。
文には著作権があります。

[Zuishin]

他人の作ったものを引用する時に出典を書くのは **常識**なので、グダグダ言うことではありません。
大学に行ったことのある人であれば普通に知っています。

書かない場合、書けない理由があるようにしか見えませんね。

[退会済みユーザー]

貴方様は当ソースコードの著作権の所有者様なのでしょうか？
その場合はそれがわかるように証明していただければ削除させていただきます。
また、気に入らないようでしたら運営様に問い合わせして削除依頼などをしてはいかがでしょうか。
そうなった場合は適当な処罰も受け入れます。
ご苦労様でした。貴重なご意見ありがとうございます。

[Zuishin]

私が所有者なら削除依頼しろ？
私が所有者じゃなければ見つかってないので何もしない？

やっぱり自分で書いたんじゃなく人のものを盗んできたんじゃないか。犯罪者。

[退会済みユーザー]

犯罪者という認識で大丈夫です。望むなら通報でもしていたいて結構です。

[Zuishin]

通報するしない、捕まる捕まらないの問題じゃない。

[Zuishin]

他人の著作物に敬意を払えないようなやつにプログラミングする資格はない。

Answer 1

i += i & -i

i & -iについては、iの最下位の立っているビットのみが1でそれ以外が0になります。
iと加算する事で最下位の立っているビットを0にし、その直上のビットに1を繰り上げます。

Answer 2

i & -i;

i が０の場合は０、それ以外は１ってことなんでしょうね

Comments

[退会済みユーザー]

addやgetSum関数の具体的な動きをお教えいただけないでしょうか

[BeatStar]

私もはっきりとわかっていませんが、それって、 &&の方では?

[episteme]

i = 0, 1, 2, 3... で i & -i の値は 0, 1, 2, 1, 4, 1, 2, 1, 8 ... ですけど。

[8524ba23]

回答する前に、デバッグ環境を整えて、実際に動きを確かめてみましょう。
デバッグ環境を使うと、ソースコードの任意の場所で実行を止め、変数のナカミを確認できます。
また、ワンステップづつ実行させてコードの動きを確認できます
そうすれば、間違った回答をせずに済むようになります