{"problem":{"name":"[EC Final 2021] Fenwick Tree","description":{"content":"Prof. Pang is giving a lecture on the Fenwick tree (also called binary indexed tree).  In a Fenwick tree, we have an array $c[1\\ldots n]$ of length $n$ which is initially all-zero ($c[i]=0$ for any $","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9883"},"statements":[{"statement_type":"Markdown","content":"Prof. Pang is giving a lecture on the Fenwick tree (also called binary indexed tree). \n\nIn a Fenwick tree, we have an array $c[1\\ldots n]$ of length $n$ which is initially all-zero ($c[i]=0$ for any $1\\le i\\le n$). Each time, Prof. Pang can call the following procedure for some position $pos$ ($1\\leq pos \\leq n$) and value $val$:\n\n```cpp\ndef update(pos, val):\n    while (pos <= n):\n        c[pos] += val\n        pos += pos & (-pos)\n```\n\nNote that `pos & (-pos)` equals to the maximum power of $2$ that divides `pos` for any positive integer `pos`. \n\nIn the procedure, $val$ can be **any real** number. After calling it some (zero or more) times, Prof. Pang forgets the exact values in the array $c$. He only remembers whether $c[i]$ is zero or not for each $i$ from $1$ to $n$. Prof. Pang wants to know what is the minimum possible number of times he called the procedure assuming his memory is accurate.\n\n## Input\n\nThe first line contains a single integer $T~(1 \\le T \\le 10^5)$ denoting the number of test cases.\n\nFor each test case, the first line contains an integer $n~(1 \\le n \\le 10 ^ 5)$. The next line contains a string of length $n$. The $i$-th character of the string is `1` if $c[i]$ is nonzero and `0` otherwise. \n\nIt is guaranteed that the sum of $n$ over all test cases is no more than $10^6$.\n\n## Output\n\nFor each test case, output the minimum possible number of times Prof. Pang called the procedure. It can be proven that the answer always exists.\n\n[samples]\n\n## Note\n\nFor the first example, Prof. Pang can call `update(1,1)`, `update(2,-1)`, `update(3,1)` in order.\n\nFor the third example, Prof. Pang can call `update(1,1)`, `update(3,1)`, `update(5,1)` in order.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9883","tags":["2021","Special Judge","O2优化","ICPC","EC Final"],"sample_group":[["3\n5\n10110\n5\n00000\n5\n11111\n","3\n0\n3\n"]],"created_at":"2026-03-03 11:09:25"}}